题目描述

单身！依然单身！吉哥依然单身！DS 级码农吉哥依然单身！所以，他生平最恨情人节，不管是 $214$ 还是 $77$，他都讨厌！

吉哥观察了 $214$ 和 $77$ 这两个数，发现：

$2+1+4=7$

$7+7=7\times 2$

$77=7\times 11$

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

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

1. 整数中某一位是 $7$；
2. 整数的每一位加起来的和是 $7$ 的整数倍；
3. 这个整数是 $7$ 的整数倍。

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

输入格式

第一行包含一个整数 $T$，表示数据组数；接下来 $T$ 行，每行包含两个正整数 $L,R$。

输出格式

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

样例

3
1 9
10 11
17 17

236
221
0

数据范围与提示

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

来源：《信息学奥赛一本通·提高篇》第五部分第 3 章 练习 3（HDU 4507）。