Palindromic Numbers
Vasya enjoys exploring various intriguing classes of numbers, and today he is delving into palindromic numbers.
A number is termed palindromic by Vasya if it reads the same forwards and backwards. Additionally, Vasya permits the addition of several (possibly zero) leading zeros to the number. For instance, the numbers 22, 4554, 12321, and 5050 are considered palindromic. Specifically, the number 5050 becomes 05050 with the addition of a leading zero, making it read the same from both directions.
Vasya is particularly interested in palindromic numbers that differ by 2. For his study, he looks for numbers x such that both x−1 and x+1 are palindromic. He refers to these numbers as inter-palindromic. Vasya seeks to determine the count of inter-palindromic numbers x within the range from L_k to R_k, inclusive, for several specified segments [L_k, R_k].
Assist Vasya with this intriguing task!
Input
The input file contains several segments of interest to Vasya. The first line contains a single integer T (1 ≤ T ≤ 2000) — the number of segments. Each of the following T lines contains two integers L_k and R_k (1 ≤ L_k ≤ R_k ≤ 10^18) — the boundaries of the segment.
Output
Output T lines. On the k-th line, output a single integer — the count of inter-palindromic numbers in the segment from L_k to R_k, inclusive.
Explanation of the example: Between 17 and 24, the palindromic numbers are 20 and 22. Thus, the only inter-palindromic number in the segment [18, 23] is 21. In the second example, the number 21 is valid again. Between 49 and 56, the palindromic numbers are 50 and 55. There are no inter-palindromic numbers in the segment [50, 55].