Jack - J97 is a boy who loves programming and is also very fond of Western architecture, as these structures are often symmetrical, with matching patterns on both the left and right sides. Jack often enjoys working on programming problems, and one day, while practicing on an online platform, he came across an interesting problem that closely matches his interests. The problem can be summarized as follows: "Given ~Q~ queries, each with two positive integers ~L~ and ~R~, the task is to count how many palindromic numbers with even lengths exist in the range ~[L, R]~. A palindromic number is a number that reads the same backward as forward." The problem is quite interesting, so J97 wanted to share it with others, and now you are tasked with solving it.

Input

• The first line contains an integer ~Q~, the number of queries.
• The following ~Q~ lines each contain two integers ~L~ and ~R~.

Output

• For each query, output the number of palindromic numbers with even lengths in the range ~[L, R]~.

Sample Input

2  
79 97  
1 100

Sample Output

1  
9

Notes

• For the range ~[79, 97]~, the only palindromic number is ~88~.
• For the range ~[1, 100]~, the palindromic numbers are: ~11, 22, 33, 44, 55, 66, 77, 88, 99~.

Constraints

• ~30\%~ of the test cases correspond to ~Q ≤ 10^2~ and ~L ≤ R ≤ 10^5~.
• ~40\%~ of the test cases correspond to ~Q ≤ 5 \times 10^3~ and ~L ≤ R ≤ 10^9~.
• ~30\%~ of the test cases correspond to ~Q ≤ 10^5~ and ~L ≤ R ≤ 10^{12}~.