单身! 依然单身! 吉哥依然单身! 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 有关:
现在问题来了:吉哥想知道在一定区间内和 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} 。