You are given an integer nn. You have to apply mm operations to it.

In a single operation, you must replace every digit dd of the number with the decimal representation of integer d + 1d+1. For example, 19121912 becomes 2102321023 after applying the operation once.

You have to find the length of nn after applying mm operations. Since the answer can be very large, print it modulo 10^9+7109+7.

Input

The first line contains a single integer tt (1 \le t \le 2 \cdot 10^51≤t≤2⋅105) — the number of test cases.

The only line of each test case contains two integers nn (1 \le n \le 10^91≤n≤109) and mm (1 \le m \le 2 \cdot 10^51≤m≤2⋅105) — the initial number and the number of operations.

Output

For each test case output the length of the resulting number modulo 10^9+7109+7.

Example

Input

5
1912 1
5 6
999 1
88 2
12 100

Output

5
2
6
4
2115

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int MAXN = 2*1e5+10,mod = 1e9+7;
long long dp[10][MAXN];
int main()
{
	int weight[10] = {10,9,8,7,6,5,4,3,2,1},Hash[10] = {0},n,m;
	string s;
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 0;i < 10; i++)
		for(int j = 0;j < MAXN; j++)  
			dp[i][j] = 1;    //初始化 
	for(int i = 0;i < MAXN-10; i++){
		dp[0][i+10] = dp[1][i+9] = (dp[0][i] + dp[1][i])%mod; //初始化 
	}
	for(int i = 2;i < 10; i++){
		for(int j = 0;j < MAXN; j++){
			if(j >= weight[i])                             // dp[i][j]表示数字i经过j次操作后数字的位数 
				dp[i][j] = (dp[1][j-weight[i]] + dp[0][j-weight[i]])%mod; //状态转移方程 
		}
	}
	while(n--){
		memset(Hash,0,sizeof(Hash)); 
		cin >> s >> m;
		int len = s.length();
		for(int i = 0;i < len; i++)
			Hash[s[i]-'0']++;  // 存放数字的个数 
		long long result = 0;
		for(int i = 0;i < 10; i++){
			result = (result + Hash[i]*dp[i][m]%mod)%mod;
		}
		cout << result << "\n";
	}
	return 0;
}