Description

军营通过烽火台传递加密军情，需将初始密码 a 转换为目标密码 b，方可解读前线战报。转换过程可使用以下三种魔法操作，每次操作消耗 K 单位的烽火燃料：
（1）移除密码 a 的最后一位数字（即 a=a/10）；
（2）在密码 a 的末尾添加一个 0（即 a=a*10）；
（3）将密码 a 的最后一位数字修改为另一个数字。
现需计算将初始密码 a 转换为目标密码 b 最少消耗的烽火燃料单位数，以确保军情快速、低成本传递。

Input

输入共三行，依次为三个正整数 a、b、k（a 和 b 为初始密码与目标密码，k 为每次操作消耗的燃料单位数）。

Output

一个整数（代表最少消耗的烽火燃料单位数）。

23456
23445
2

8

12345
12345
8

0

【样例1解释】

第1次，a变为：2345；
第2次，a变为：2344；
第3次，a变为：23440；
第4次，a变为：23455；
4次*2=8。

【数据范围】

20% ，1≤a,b≤10；
70% ，1≤a,b≤10^18；
100% ，1≤a,b≤10^1000000，1≤k≤10^6；
保证 a,b 的位数相同。