#170. 「一本通 5.3 练习 3」恨 7 不成妻

「一本通 5.3 练习 3」恨 7 不成妻

题目描述

原题来自:HDU 4507

单身!
依然单身!
吉哥依然单身!
DS 级码农吉哥依然单身!
所以,他平生最恨情人节,不管是 214214 还是 7777,他都讨厌!

吉哥观察了 2142147777 这两个数,发现:

$$\begin{align} 2+1+4&=7\\ 7+7&=7\times 2\\ 77&=7\times 11 \end{align} $$

最终,他发现原来这一切归根到底都是因为和 77 有关!所以,他现在甚至讨厌一切和 77 有关的数!

什么样的数和 77 有关呢?如果一个整数符合下面三个条件之一,那么我们就说这个整数和 77 有关:

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

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

输入格式

输入数据的第一行是测试数据组数 TT,然后接下来的 TT 行表示 TT 组测试数据。

每组数据在一行内包含两个正整数 L,RL, R

输出格式

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

样例

3
1 9
10 11
17 17
236
221
0

数据范围与提示

对于全部数据,1T50,1LR10181\le T\le 50,1\le L\le R\le 10^{18}