题目描述

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

$\begin{align}2+1+4&=7 \\ 7+7&=7 \times2 \\ 77&=7 \times11 \end{align}$

最终，他发现原来这一切归根到底都是因为和7有关！所以，他现在甚至讨厌一切和7有关的数！ 什么样的数和7有关呢？如果一个整数符合下面三个条件之一，那么我们就说这个整数和7有关：

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

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

输入描述

输入数据的第一行是测试数据组数T，然后接下来的T行表示T组测试数据。 每组数据在一行内包含两个正整数L,R。

输出描述

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

示例1

输入

3
1 9
10 11
17 17

输出

236
221
0

备注

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