Description

XMU的人生赢家森爷在脱单之后发现，情人节与七夕是两个传统的秀恩爱节日，这两个节日有如下特点：
2+1+4=7
77=7*11
所以这两个节日都和7有非常紧密的关系。

他回归单身后，痛定思痛，决定将概念拓展，创造出love number，“love number”是符合以下定义（满足一条即可）的数字：
数字中某一位是7
数字的每一位加起来能被7整除
这个数字是7的整数倍。

作为FFF团的一员，你非常讨厌love number，因此你想知道在一定区间内所有非love number的数字的平方和。

Format

Input

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

Output

每组测试数据输出一行，[L,R]中非love number数字的平方和，并将结果对10^9 + 7 求模后输出

Sample 1

Input

3
1 9
10 11
17 17

Output

236
221
0

Limitation

1s, 128MB for each test case.

Hint

Source

CYH