Description

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]$.

Input Format

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 Format

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.

3
1 5
3 9
8 8

2
2
0

Hint

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

Translated by ChatGPT 5