You are given an integer n. You have to apply m operations to it.

In a single operation, you must replace every digit d 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 n after applying m 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.

Example

Input


5
1912 1
5 6
999 1
88 2
12 100


Output


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.

For the third test, 999 becomes 101010 after 1 operation which is of length 6.

For the fourth test, 88 becomes 1010 after 2 operations which is of length 4.
import java.io.*;
import java.util.*;

public class C {

	public static void main(String[] args) {
        FastScanner in = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int t = in.nextInt(), tt = 0;
        dp = new long[10][2_000_01];
        for(int j=0;j<=2_000_00;j++){
        	for(int i=0;i<10;i++){
        		/*if(j==0){
        			dp[i][j] = 1;	
        		}
         	  	else if(i!=9){
         	  		dp[i][j] = dp[i+1][j-1]; 
         	  	}
         	  	else dp[i][j] = (dp[1][j-1] + dp[0][j-1])%mod;
         	  	*/
         	  	dp[i][j] = dfs(i,1,j);
        	}
        }	
        while(t-->0) { 
            int n = in.nextInt(), m = in.nextInt();
            long ans = 0;
            while(n>0){                
            	//out.println(n%10+" "+y);
            	ans = (ans + dp[n%10][m])%mod;
            	n/=10;
            }
            out.println(ans);
    		tt++;
    		//out.println("Case #"+tt+": "+ans);
        }
        out.flush();
	}

	static long mod = (long)1e9+7, dp[][];

	static long dfs(int n, int x, int m){
		if(dp[n][m]!=0) return dp[n][m];
		if(m>=10-n){
			return (dfs(1,x+1,m-(10-n)) + dfs(0,x+1,m-(10-n)))%mod;		
		}
		else return 1;
	}
	
	static class FastScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		
		String next() {
			while(!st.hasMoreTokens())
				try { st = new StringTokenizer(br.readLine()); }
				catch(IOException e) {}
			return st.nextToken();
		}
		
		String nextLine(){
			try{ return br.readLine(); } 
			catch(IOException e) { } return "";
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		
		long nextLong() {
			return Long.parseLong(next());
		}
		
		int[] readArray(int n) {
			int a[] = new int[n];
			for(int i=0;i<n;i++) a[i] = nextInt();
			return a;
		}
	}

	static final Random random = new Random();

	static void ruffleSort(int[] a){
		int n = a.length;
		for(int i=0;i<n;i++){
			int j = random.nextInt(n), temp = a[j];
			a[j] = a[i]; a[i] = temp;
		}
		Arrays.sort(a); 	
	}
}
