2870: 「一本通 5.3 练习 3」恨 7 不成妻

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:88 Solved:28

Description

原题来自:HDU 4507

单身!
依然单身!
吉哥依然单身!
DS 级码农吉哥依然单身!

所以,他平生最恨情人节,不管是 $214$ 还是 $77$,他都讨厌!

吉哥观察了 $214$ 和 $77$ 这两个数,发现:$$2+1+4=7\quad 7+7=7 \times 2\quad 77=7 \times 11$$

最终,他发现原来这一切归根到底都是因为和 $7$ 有关!所以,他现在甚至讨厌一切和 $7$ 有关的数!

什么样的数和 $7$ 有关呢?如果一个整数符合下面三个条件之一,那么我们就说这个整数和 $7$ 有关:

    整数中某一位是 $7$;
    整数的每一位加起来的和是 $7$ 的整数倍;
    这个整数是 $7$ 的整数倍。

现在问题来了:吉哥想知道在一定区间内和 $7$ 无关的数字的平方和。

Input

输入数据的第一行是测试数据组数 $T$,然后接下来的 $T$ 行表示 $T$ 组测试数据。

每组数据在一行内包含两个正整数 $L,R$。

Output

对于每组数据,请计算 $[L,R]$ 中和 $7$ 无关的数字的平方和,并将结果对 $10^9+7$ 取模后输出。

Sample Input Copy

3
1 9
10 11
17 17

Sample Output Copy

236
221
0

HINT

对于全部数据,$1 \leq T \leq 50,1 \leq L \leq R \leq 10^{18}$。

加入题单

上一题 下一题 算法标签: