Any number is called beautiful if it consists of $2N$ digits and the sum of the first $N$ digits is equal to the sum of the last $N$ digits. Your task is to find the count of beautiful numbers in the interval from $L$ to $R$ (including $L$ and $R$).

Beautiful numbers do not have leading zeroes.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains two space-separated integers $L$ and $R$ denoting the range interval $[L,R]$.

Output format

For each test case, print the count of beautiful numbers in a new line.

Constraints

$1 \le T \le 200000\\ 1 \le L \le R \le 1000000000$