题目描述

给你一个由区间 $[l,r]$ 范围内的所有整数构成的数列 $l, l+1, l+2, \ldots, r$，你需要将数列分成连续的若干段，使得每一段中所有数字的数位和之和都 $\ge k$。

问：最多能够分成多少段？

说明：本题中，一个数的数位和指的是它的十进制表示中各位上的数字之和。比如：$123$ 的数位和为 $1+2+3 = 6$，$365$ 的数位和为 $3+6+5=14$。

输入格式

输入共一行，包含三个整数 $l,r,k$，两两之间以一个空格分隔（$1 \le l \le r \le 10^{18}, 1 \le k \le 1000$）。

输出格式

若 $[l,r]$ 范围内的所有数的数位和之和 $\lt k$，输出 $0$；
否则，输出一个整数，表示这些数最多能够分成连续的多少段，且满足每一段中所有数的数位和之和 $\ge k$。

样例

1 10 5

6

21 35 100

0

40 218 57

29

样例解释

• 样例1：$[1,3]$, $[4,5]$, $[6,6]$, $[7,7]$, $[8,8]$, $[9,10]$；
• 样例2：整段 $[21, 35]$ 范围内的数字的数位和之和（$96$）都没有达到 $100$；
• 样例3：$[1,47]$, $[48,54]$, $[55,59]$, $[60,66]$, $[67,71]$, $[72,77]$, $[78,82]$, $[83,87]$, $[88,92]$, $[93,97]$, $[98,106]$, $[107,116]$, $[117,125]$, $[126,132]$, $[133,138]$, $[139,145]$, $[146,151]$, $[152,157]$, $[158,163]$, $[164,168]$, $[169,174]$, $[175,178]$, $[179,183]$, $[184,187]$, $[188,192]$, $[193,196]$, $[197,201]$, $[202,209]$, $[210,218]$。

数据范围

• 对于 $10\%$ 的数据，$1 \le l \le r \le 100$；
• 对于 $20\%$ 的数据，$1 \le l \le r \le 1000$；
• 对于 $40\%$ 的数据，$1 \le l \le r \le 10^9$；
• 对于 $100\%$ 的数据，$1 \le l \le r \le 10^{18}, 1 \le k \le 1000$。