Description

Original source: HDU 4507

Single!
Still single!
Brother Ji is still single!
DS-level coder Brother Ji is still single!
Thus, he despises Valentine's Day the most, whether it's $214$ or $77$, he hates them all!

Brother Ji observed the numbers $214$ and $77$ and found:

$$\begin{align} 2+1+4&=7\\ 7+7&=7\times 2\\ 77&=7\times 11 \end{align} $$

Eventually, he realized that all of this boils down to their connection with the number $7$! Therefore, he now even hates all numbers related to $7$!

What kind of numbers are related to $7$? If an integer meets any of the following three conditions, we say it is related to $7$:

1. One of its digits is $7$;
2. The sum of its digits is a multiple of $7$;
3. The integer itself is a multiple of $7$.

Now the question arises: Brother Ji wants to know the sum of the squares of numbers within a certain interval that are unrelated to $7$.

Input Format

The first line of input data is the number of test cases $T$, followed by $T$ lines representing $T$ test cases.

Each case consists of two positive integers $L$ and $R$ on a single line.

Output Format

For each test case, compute the sum of the squares of numbers in $[L,R]$ that are unrelated to $7$, and output the result modulo $10^9+7$.

Sample 1

3
1 9
10 11
17 17

236
221
0

Data Range and Hints

For all data, $1\le T\le 50,1\le L\le R\le 10^{18}$.