说明

军营通过烽火台传递加密军情，需将初始密码 a 转换为目标密码 b，方可解读前线战报。转换过程可使用以下三种魔法操作，每次操作消耗 K 单位的烽火燃料：

（1）移除密码 a 的最后一位数字（即 a=a/10）；

（2）在密码 a 的末尾添加一个 0（即 a=a*10）；

（3）将密码 a 的最后一位数字修改为另一个数字。

现需计算将初始密码 a 转换为目标密码 b 最少消耗的烽火燃料单位数，以确保军情快速、低成本传递。

【样例1解释】

第1次，a变为：2345；

第2次，a变为：2344；

第3次，a变为：23440；

第4次，a变为：23445；

4次*2=8。

【样例输入 2】

12345

12345

8

【样例输出 2】

0

【数据范围】

20% ，1≤a,b≤10；

70% ，1≤a,b≤10^18；

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

输入格式

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

输出格式

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

23456
23445
2

8

提示