B. Mode
time limit per test
1 с
memory limit per test
512 megabytes
input
standard input
output
standard output

Walk Alone likes to go with the flow, so he designs a function on digits about mode.

Let $$$f(x)$$$ be the maximal occurrence among the digits in decimal expression of the number $$$x$$$. For example, $$$f(133)=2$$$ since digit $$$3$$$ occurs twice, while $$$f(213)=f(0)=1$$$ since every digit appears exactly once in both numbers. Walk Alone gives you a task to calculate the range sum of function $$$f$$$, i.e. $$$\sum_{i=l}^r f(i)$$$.

Input

The first line contains one integer $$$T$$$ ($$$1\le T\le 10^3$$$) — the number of test cases. Next $$$T$$$ test cases follow.

The first and only line of each test cases contains two integers $$$l, r$$$ ($$$0 \le l \le r \le 10^{18}$$$) — the range of the calculation.

Output

For each test case, print a single integer in a line denoting the sum.

Example
Input
3
1 20
5 199
0 1000000000
Output
21
233
2553052375