Problem Description

$\text{Anica}$ has a mysterious infinite table with infinitely many rows and infinitely many columns. Interestingly, each number appears only a finite number of times in the table.

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

The number $A(i,j)$ in row $i$ and column $j$ of the table is defined as follows:

• $A(i,1)=i$

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

Now $\text{Anica}$ gives $Q$ queries. Each query provides two integers $L$ and $R$. Please find how many numbers in the infinite table have values within $\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 one integer. The $i$-th line should be the answer to the $i$-th query.

2
1 10
5 8

18
8

3
17 144
121 121
89 98

265
25
10

1
1 1000000000

1863025563

Hint

Constraints

For $50\%$ of the testdata, $1\le L,R\le 10^6$.

For $100\%$ of the testdata, $1\le Q\le 10^5$, $1\le L,R\le 10^{10}$.

Source

Translated from COCI 2015-2016 CONTEST #6 T6 SAN.

This problem uses the original COCI scoring. Full score is $160$..

Translated by ChatGPT 5