K. Dibonacci Numbers
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Litusiano was pooing when he came up with the following problem:

Given $$$l$$$ and $$$r$$$, you have to count how many dibonacci numbers are in the range $$$[l, r]$$$.

A dibonacci number is an integer whose digits are the sum modulo $$$10$$$ of the two previous digits.

For example, $$$123$$$ is a dibonacci number, because $$$(1 + 2)$$$ mod $$$10 = 3$$$, $$$471$$$ is also a dibonacci number because $$$(4 + 7)$$$ mod $$$10 = 1$$$ and $$$2169$$$ is not a dibonacci number because $$$(1 + 6)$$$ mod $$$10 = 7$$$, which is different from $$$9$$$.

Note that all the positive integers $$$\leq 99$$$ are also dibonacci numbers.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 69 \cdot 10^{4})$$$. The description of the test cases follows.

For each test case:

There is a line consisting of two integers $$$l, r$$$ $$$(1 \leq l \leq r \leq 10^{18})$$$ — the asked range.

Output

For each test case, output how many dibonacci numbers are in the given range.

Example
Input
5
2 7
1 124
6 977733
7773 36969
100000000 1000000000
Output
6
102
452
49
90
Note

In the first test case, the answer is $$$6$$$ because all the numbers in the range $$$[2, 7]$$$ are dibonacci numbers.

In the second case, there are $$$102$$$ dibonacci numbers in the range $$$[1, 124]$$$, like $$$101$$$ or $$$69$$$.