Problem D
Palindrome Dreams

Erfan is very passionate about palindrome numbers. A palindrome number is any number that reads the same when reading it from left to right and from right to left. For example, the number “139931” is a palindrome, while “139391” is not.

His passion is actually more like an obsession, while daydreaming at random times during the day and also right before going to sleep Erfan likes to count palindrome numbers (some people fall asleep by counting sheep, who are we to judge?)

This obsession is making it hard for Erfan to be productive during the day, so he asks you to write a program that will make this counting easier for him.

Specifically, you are asked to write a program that takes a number of queries, where each query is in the form of two posive integers $A$ and $B$, and you are asked to count how many palindrome numbers are there in the $[A, B]$ range (extremes included).

Input

The first line contains one integer: $N$, the number of queries that Erfan would like you to answer for him.

Each of the next $N$ lines contain two positive integers $A_ i$ and $B_ i$.

Output

You need to write $N$ lines, each containing the answer to the corresponding query.

Constraints

• $1 \le N \le MAXN = 100\, 000$.

• $1 \le A \le B \le 10\, 000\, 000$.

5
11 22
111 222
1 1000
9 10
99 101

2
12
108
1
2