题目描述

单身!
依然单身！
吉哥依然单身！
\(DS\)级码农吉哥依然单身！
所以，他生平最恨情人节，不管是\(214\)还是\(77\)，他都讨厌！
　　
吉哥观察了\(214\)和\(77\)这两个数，发现：

2+1+4=7
7+7=7*2
77=7*11

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

什么样的数和\(7\)有关呢？

如果一个整数符合下面\(3\)个条件之一，那么我们就说这个整数和\(7\)有关
\(1、\)整数中某一位是\(7\)；
\(2、\)整数的每一位加起来的和是\(7\)的整数倍；
\(3、\)这个整数是\(7\)的整数倍；

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

格式

输入格式

输入数据的第一行是\(case\)数\(T(1 <= T <= 50)\)，然后接下来的\(T\)行表示\(T\)个\(case\);
每个\(case\)在一行内包含两个正整数\(L, R(1 <= L <= R <= 10^18)\)。

输出格式

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

样例1

输入样例1

3
1 9
10 11
17 17

输出样例1

236
221
0

来源

HDU4507
信息学奥赛一本通1590
数据可参考：
LOJ10168