F. Happy Numbers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an operation that changes an integer to the sum of the square of all its digits. This operation can be applied to a positive integer as many times as you like.

If a number can become $$$1$$$ after any amount of operations (possibly zero), it is said to be a happy number. A happy number, for instance, is $$$13$$$, which becomes $$$10(1^2 + 3^2 = 10)$$$ after one operation and becomes $$$1(1^2 + 0^2 = 1)$$$ after one more operation. However, $$$2, 3$$$, and $$$4$$$ are not happy numbers.

You are given $$$t$$$ closed intervals, each represented by two integers $$$l_i$$$ and $$$r_i$$$ $$$(1 \leq i \leq t)$$$. For each interval, please determine the number of happy numbers in the interval.

Formally, for each query $$$i$$$, please compute

$$$$$$\sum_{x=l_i}^{r_i}f(x)$$$$$$

where $$$f(x)=1$$$ if $$$x$$$ is a happy number and $$$f(x)=0$$$ if $$$x$$$ is not a happy number.

Since the answers can be very large, please print them modulo $$$10^9+7$$$.

Input

The first line contains one integer $$$t$$$ $$$(1 \leq t \leq 100)$$$ — the number of test cases.

The only line of each test case contains two integers $$$l_i, r_i$$$ $$$(1 \leq l_i \leq r_i \leq 10^{200})$$$.

It is guaranteed that the sum of the lengths of all inputted integers does not exceed $$$10^3$$$.

Output

Print $$$t$$$ lines, each containing one integer — the number of happy numbers in the given closed interval, modulo $$$10^9+7$$$.

Example
Input
4
7 7
5 10
1 1000
1 999999
Output
1
2
143
143070
Note

In the first range, $$$7$$$ is a happy number because $$$7^2=49$$$; $$$4^2+9^2=97$$$; $$$9^2+7^2=130$$$; $$$1^2+3^2+0^2=10$$$; $$$1^2+0^2=1$$$.

In the second range, the two happy numbers are $$$7, 10$$$.