P7802 [COCI 2015/2016 #6] SAN

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

The first line contains an integer $Q$. The next $Q$ lines each contain two integers $L$ and $R$.

Output $Q$ lines, each containing one integer. The $i$-th line should be the answer to the $i$-th query.

**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](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #6](https://hsin.hr/coci/archive/2015_2016/contest6_tasks.pdf) T6 SAN**. **This problem uses the original COCI scoring. Full score is $160$.**. Translated by ChatGPT 5