题目描述

原题来自：HDU 4507

单身！

依然单身！

吉哥依然单身！

DS 级码农吉哥依然单身！

所以，他平生最恨情人节，不管是 \(214\) 还是 \(77\)，他都讨厌！

吉哥观察了 \(214\) 和 \(77\) 这两个数，发现：
\[
\begin{align}
2+1+4&=7\\
7+7&=7\times 2\\
77&=7\times 11
\end{align}
\]
最终，他发现原来这一切归根到底都是因为和 \(7\) 有关！所以，他现在甚至讨厌一切和 \(7\) 有关的数！

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

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

输入格式

输入数据的第一行是测试数据组数 \(T\)，然后接下来的 \(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}\)。