Migrated from Lutece 116 Beautiful Palindromes

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

A number is called palindrome if it reads the same forwards as backwards. A palindrome number is called beautiful if it has no adjacent digits of the same. For example, 11 is a palindrome, but it is NOT a beautiful palindrome. 989 is a beautiful palindrome.

Hongshu loves beautiful palindromes so much that he wants to know the number of beautiful palindromes between $A$ and $B$ (inclusive). The range may be very large, so he asks you for help.

Input

The first line of the input is a integer $T$ ($T\leq 989$), which stands for the number of test cases you need to solve. Each case consists of two integers $A$, $B$ ($0\leq A\leq B < 2^{64}$) on a single line.

Output

For each case, print the number of beautiful palindromes in $[A, B]$.

Samples

2
1 10
1 100

9
9

Resources

The 8th UESTC Programming Contest Final