Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4044
How Many Palindromes

Time Limit: 1 Second      Memory Limit: 65536 KB

Consider representing a date in the format YMMDD, where Y is the year without leading zeros, MM is the two-digit month, and DD is the two-digit day of the month. For example, 20180610, which means June 10th, year 2018; Or even 1234560610, which means June 10th, year 123456.

Your task is to calculate the number of palindromes in all the dates between Y1M1M1D1D1 and Y2M2M2D2D2 (both inclusive).

To simplify this problem, you don't need to take leap years into consideration. That is to say, in this problem, February in every year always has only 28 days.

A palindrome is a string that can be read the same way from left to right and from right to left. For example, '92400429' and '212131212' are both palindromes.

Input

There are multiple test cases. The first line of the input is an integer $T$ ($1 \le T \le 10^4$), indicating the number of test cases. For each test case:

The first and only line contains two dates Y1M1M1D1D1 and Y2M2M2D2D2 ($2000 \le Y_1, Y_2 < 10^{18}$), their meanings are described above.

It's guaranteed that the first date is not larger than the second date, and both dates are valid.

Output

For each test case, you should output one line containing one integer, indicating the answer of this test case.

Sample Input

4
9240000429 9240990429
92200228 92200301
20180610 1234560610
1234567890101 9876543211231

Sample Output

10
0
3884
300000

Hint

For the first sample test case, the 10 palindromic dates are: 9240000429, 9240110429, 9240220429, ..., 9240990429.

For the second sample test case, note that in this problem, we don't take leap years into consideration. So 92200229 is not a valid date and is thus ignored.


Author: WENG, Caizhi
Source: ZOJ Monthly, June 2018
Submit    Status