For an integer $x$ where $x \ge 10$, it can be split into two parts as follows: Represent $x$ as a decimal string. Split the string at some position into two non-empty strings such that neither string has leading zeros. * Treat these two strings as decimal integers, denoted as $x_1$ and $x_2$.

Let $f(x)$ be the sum of the digits of $x$, and $g(x)$ be the minimum value of $|f(x_1) - f(x_2)|$ among all possible splits, where $|p|$ denotes the absolute value of $p$.

Given $l$ and $r$, calculate $\sum_{x=l}^{r} g(x)$.

Input

The input contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 1000$). For each test case, the input contains two integers $l$ and $r$ ($10 \le l \le r \le 10^{18}$).

Output

For each test case, output one integer representing the sum.

Examples

Input 1

5
108 112
10 1000
10 10000
10 100000
114514 1919810

Output 1

16
3136
31636
316636
5715693

Note

For the first test case: $g(108) = |f(10) - f(8)| = |1 - 8| = 7$, $g(109) = |f(10) - f(9)| = |1 - 9| = 8$, $g(110) = \min(|f(1) - f(10)|, |f(11) - f(0)|) = \min(|1 - 1|, |2 - 0|) = 0$, $g(111) = \min(|f(1) - f(11)|, |f(11) - f(1)|) = \min(|1 - 2|, |2 - 1|) = 1$, * $g(112) = \min(|f(1) - f(12)|, |f(11) - f(2)|) = \min(|1 - 3|, |2 - 2|) = 0$.