Description

Xiao Z listed many numbers on scratch paper. He calls an integer a $k$-compact number if the absolute difference between every pair of adjacent digits does not exceed $k$.

Now Xiao Z wants to know how many $k$-compact numbers are within $[l, r]$ and asks for your help.

Input Format

A single line with three integers $l, r, k$.

Output Format

A single line containing one integer: the number of $k$-compact numbers in $[l, r]$.

1 13 1

12

Hint

Sample explanation: within $[1, 13]$, only $13$ is not a $1$-compact number.

For $30\%$ of the testdata, $r - l \le 10^5$.

For another $30\%$ of the testdata, $l = 1$, and $r$ is a multiple of $10$.

For $100\%$ of the testdata, $1 \le l \le r \le 10^{18}$, $0 \le k \le 8$.

Translated by ChatGPT 5