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)$$$.
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}$$$).
For each test case, output a single integer in a line — $$$f(L, R)$$$.
42 410 121 999999999999999910000000000000000 10000000000000000
2014566666666666666611