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+1. For example, 1912 becomes 21023 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+7.

Input

The first line contains a single integer t(1<t<=2*10^5) — the number of test cases.

The only line of each test case contains two integers n (1<n<10^9) and m(1<=m<=2*10^5) — the initial number and the number of operations.

Output

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

Sample 1

5
1912 1
5 6
999 1
88 2
12 100

5
2
6
4
2115

Note

For the first test, 1912 becomes 21023 after 1 operation which is of length 5.

For the second test, 5 becomes 21 after 6 operations which is of length 2.

思路

本题数据较大，需要考虑多个方面，预处理时用当数字为10时进行操作的dp,用sum数组存储进行多少次后有多少个数字；询问时只需要判断各个是否达到10，未达到则还是一位数字，达到则直接访问sum数组。

本题的状态转移方程在预处理上

状态转移方程为：if(j==0)dp[i][j]=dp[i-1][9]%mod;//0由9转移来
                             else if(j==1)dp[i][j]=(dp[i-1][0]+dp[i-1][9])%mod;//1由9和0转移来
                             else dp[i][j]=dp[i-1][j-1]%mod;//其他由j-1转移来

代码

#include<bits/stdc++.h>
const int mod=1e9+7;
int main(){
	long long int T,n,m,answer,dp[200010][10],sum[200010]={0};
	scanf("%lld",&T);
	dp[0][0]=1;dp[0][1]=1;sum[0]=2;//初始化为10的时候 
    	for(int i=1;i<=200000;i++){
		   for(int j=0;j<=9;j++){
		   	   if(j==0)dp[i][j]=dp[i-1][9]%mod;
		   	   else if(j==1)dp[i][j]=(dp[i-1][0]+dp[i-1][9])%mod;
		       else dp[i][j]=dp[i-1][j-1]%mod;
		       sum[i]=(sum[i]+dp[i][j])%mod;
		   }
		}//预处理 
	while(T--){
		answer=0; 
		int t[10]={0},a[10]={0};
		scanf("%lld %lld",&n,&m);
		while(n>0){
			int tem=n%10;
			t[tem]++;
			n/=10;
	    }
	     for(int i=0;i<=9;i++)a[i]=10-i;//初始化每个数字到10的次数 
		 	for(int j=0;j<10;j++){
		 		 if(m>=a[j]){
				  answer=(answer+(t[j]*sum[m-a[j]])%mod)%mod;//如果操作次数m大于当前j到10的次数，则当前数字个数乘dp次数； 
		 	     }
				  else if(m<a[j])answer=(answer+t[j])%mod;//否则直接加上当前个数。 
			 }
		    printf("%lld\n",answer);	 
		} 		
	return 0;
}