Description

单身!依然单身！吉哥依然单身！DS 级码农吉哥依然单身！所以，他生平最恨情人节，不管是 $214$ 还是 $77$，他都讨厌！

吉哥观察了 $214$ 和 $77$ 这两个数，发现：

$2+1+4=7$

$7+7=7\times 2$

$77=7\times 11$

最终，他发现原来这一切归根到底都是因为和 $7$ 有关！所以，他现在甚至讨厌一切和 $7$ 有关的数！ 什么样的数和 $7$ 有关呢？

如果一个整数符合下面 $3$ 个条件之一，那么我们就说这个整数和 $7$ 有关——

1.整数中某一位是 $7$；

2.整数的每一位加起来的和是 $7$ 的整数倍；

3.这个整数是 $7$ 的整数倍；

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

Input

输入数据的第一行是 case 数 $T$($1 \le T \le 50$)，然后接下来的 $T$ 行表示 $T$ 个 case;

每个 case 在一行内包含两个正整数 $L$，$R$($1 \le L \le R \le 10^18$)。

Output

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

Sample Input

3

1 9

10 11

17 17

Sample Output

236

221

0

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 500 , mod = 1e9 + 7;
int t;
int l , r;
int dp[MAXN][MAXN][MAXN];
int dig[MAXN];

int dfs(int pos , int x , int sum , bool flag , int pre , bool yes) {
	if(pos < 1) {
		if(x % 7 == 0 || sum % 7 == 0 || yes)
			return x * x % mod;
		return 0;
	}
	if(!flag && dp[pos][pre][sum] != -1)
		return dp[pos][pre][sum];
	int up = flag ? dig[pos] : 9;
	int ans = 0;
	for(register int i = 0;i <= up;i ++)
		if(i == 7)
			ans = (ans + dfs(pos - 1 , x * 10 + i , sum + i , i == dig[pos] && flag , i , true)) % mod;
		else
			ans = (ans + dfs(pos - 1 , x * 10 + i , sum + i , i == dig[pos] && flag , i , yes)) % mod;
	if(!flag)
		dp[pos][pre][sum] = ans % mod;
	return ans % mod;
}

inline int solve(int x) {
	int cnt = 0;
	while(x) {
		dig[++ cnt] = x % 10;
		x /= 10;
	}
	return dfs(cnt , 0 , 0 , true , 0 , false);
}

inline int s(int n) {
	return ((n * (n + 1) * (2 * n + 1)) % mod * 166666668) % mod;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(dp , -1 , sizeof(dp));
	for(register int i = 1;i <= 10050;i ++)
		cout << solve(i) << " ";
	exit(0);
	cin >> t;
	while(t --) {
		cin >> l >> r;
		cout << (s(r) + mod - solve(r) + mod - s(l - 1) + solve(l - 1)) % mod << '\n';
	}
	return 0;
}