A. Obsession With Functions
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Yeamin loves to play with functions. Recently, he has been experimenting with functions defined on integers.

The function $$$s(x)$$$ denotes the sum of the decimal digits of a positive integer $$$x$$$. For example, $$$s(125) = 1 + 2 + 5 = 8$$$.

Another function $$$h(x)$$$ repeatedly uses $$$s(x)$$$ until the result is a single-digit integer. Formally, $$$$$$ h(x) = \begin{cases} x, & x \lt 10,\\ h(s(x)), & x \ge 10. \end{cases} $$$$$$ For example, $$$h(987) = h(9+8+7) = h(24) = h(2+4) = h(6) = 6$$$.

To make things more interesting, Yeamin defines a new function $$$\displaystyle f(L,R) = \sum_{x=L}^{R} h(x^2)$$$ for integers $$$L$$$ and $$$R$$$ with $$$1 \le L \le R$$$. For example, $$$f(2,4) = h(2^2) + h(3^2) + h(4^2) = h(4) + h(9) + h(16) = 4 + 9 + 7 = 20$$$.

Now, Yeamin wants to compute $$$f(L, R)$$$ for multiple pairs of $$$L$$$ and $$$R$$$. Given the values of $$$L$$$ and $$$R$$$, determine $$$f(L,R)$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

Each test case consists of a single line containing two space-separated integers $$$L$$$ and $$$R$$$ ($$$1 \le L \le R \le 10^{16}$$$).

Output

For each test case, output a single integer in a line — $$$f(L, R)$$$.

Example
Input
4
2 4
10 12
1 9999999999999999
10000000000000000 10000000000000000
Output
20
14
56666666666666661
1