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\)