P4193 Numbers

Xiao D's favorite numbers have the following property. Let $n$ be a positive integer, let $S(n)$ be the sum of the digits of $n$, and define $D(n)$ as follows. $$ D(n) = \begin{cases} \displaystyle S(n) & S(n) < 10 \\ \displaystyle D(S(n)) & S(n) > 10 \end{cases} $$ Every number that Xiao D likes can be written in the form $x \times D(x)$ (that is, if a number $A$ is liked, then there exists a number $x$ such that $A = x \times D(x)$). Xiao D wants to know how many numbers he likes in the interval $[L, R]$.

The first line contains an integer $T$, the number of test cases. The next $T$ lines each contain two numbers $L$ and $R$ (the interval is guaranteed to be valid), representing the query $[L, R]$.

Output $T$ lines, each with a single number, indicating how many numbers Xiao D likes appear in this interval. You will receive full score for a test point if and only if your output exactly matches the standard output.

For $100\%$ of the testdata, $L, R \le 10^{18}$ and $T \le 20$. Translated by ChatGPT 5