Mystic Infinite Rev Table Queries

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

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

The table is defined as follows:

• \(A(i,1)=i\).
• For \(j>1\), \(A(i,j)=A(i,j-1)+\mathrm{rev}(A(i,j-1))\).

You are given \(Q\) queries. Each query consists of two integers \(L\) and \(R\). For each query, determine how many numbers that appear anywhere in the infinite table have values between \(L\) and \(R\) (inclusive).

Note: It is guaranteed that each number appears only finitely many times in the table.

inputFormat

The first line contains one integer \(Q\), representing the number of queries. Each of the next \(Q\) lines contains two integers \(L\) and \(R\) separated by a space.

Data Constraints (for practical simulation): The maximum \(R\) among all queries is reasonably small (for example, \(R\) \(\le\) 10⁵).

outputFormat

For each query, output a single integer on a new line, the count of numbers (which occur in the infinite table) whose values lie between \(L\) and \(R\) (inclusive).

sample

3
1 10
1 100
50 100

10
22
9