题目描述

单身！ 依然单身！ 吉哥依然单身！ DS 级码农吉哥依然单身！ 所以，他平生最恨情人节，不管是 $214$ 还是 $77$，他都讨厌！ 吉哥观察了 $214$ 和 $77$ 这两个数，发现： $2+1+4=7$ $7+7=7 ×2$ $77=7 × 11$ 最终，他发现原来这一切归根到底都是因为和 $77$ 有关！所以，他现在甚至讨厌一切和 $7$ 有关的数！ 什么样的数和 $7$ 有关呢？如果一个整数符合下面三个条件之一，那么我们就说这个整数和 $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≤T≤50,1≤L≤R≤10^{18}$ 。

评测数据说明

本题使用经输入域与独立答案完整核验的第三方公开训练数据，并补充自编边界及公开样例，共10个测试点，非原站或官方原始数据。总分100分。公开训练数据来自HEEKDragonOne/ACM固定提交，逐点来源与SHA256保存在教师复核材料。