P2188 Xiao Z's k-compact numbers

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.

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

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

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