Problem Description

Anica has a mysterious infinite table with infinite rows and columns. Interestingly, each number in the table appears a finite number of times.

Define the function $\mathrm{rev}(i)$, which returns the new number obtained by reversing $i$ in its decimal representation. For example, $\mathrm{rev}(213)=312$ and $\mathrm{rev}(406800)=008604=8604$.

The number $A(i,j)$ at the $i$-th row and $j$-th column of the table is obtained as follows:

• $A(i,1)=i$
• $A(i, j) = A(i, j − 1)+\mathrm{rev}\big(A(i,j-1)\big)$ for $j>1$

Now, Anica gives $Q$ queries, each query consisting of two integers $L$ and $R$. You are to find out how many numbers in the infinite table fall within the range $\big[L,R\big]$.

Input Format

The first line contains an integer $Q$.

The next $Q$ lines each contain two integers $L$ and $R$.

Output Format

Output $Q$ lines, each containing a single integer, where the $i$-th line is the answer to the $i$-th query.

Sample Input and Output

Sample Input #1

2
1 10
5 8

Sample Output #1

18
8

Sample Input #2

3
17 144
121 121
89 98

Sample Output #2

265
25
10

Sample Input #3

1
1 1000000000

Sample Output #3

1863025563

Notes

[Data Range]

For 50% of the data, it is guaranteed that $1\le L,R\le 10^6$.

For 100% of the data, it is guaranteed that $1\le Q\le 10^5$ and $1\le L,R\le 10^{10}$.

[Problem Source]

This problem is translated from COCI 2015-2016 CONTEST #6 T6 SAN.

This problem is scored according to the original COCI settings, with a maximum score of $160$.

见题面 Input 部分

见题面 Output 部分