题目描述

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

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

• $\red{2+1+4=7}$
• $\red{7+7=7×2}$
• $\red{77=7×11}$ ​

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

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

3
1 9
10 11
17 17

输出样例

236
221
0

提示

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