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.util.*;
import java.io.*;
import java.lang.*;

public class cf714 {

//HashMap<Integer,Integer> hm=new HashMap<>();
//ArrayList<Integer> list=new ArrayList<>();
//HashSet<Integer> hs=new HashSet<>();
//Stack<Integer> st=new Stack<>();
//Queue<Integer> q=new LinkedList<>();
//PriorityQueue<Integer> pq=new PriorityQueue<>();
// static ArrayList<ArrayList<Integer>> gp=new ArrayList<>();
//int[] arr=new int[n];
//System.out.println("YES");
//1 hr- atleast 2 qs d-2
//Mt_do 3 qs d-2  
//Mt_do 4 qs d-3
//StringBuilder sb=new StringBuilder();

static long mod=1000000007;

public static long fact(long n){

    long ans=1;

    for(long i=1;i<=n;i++){
        ans=(ans*i)%mod;
    }
    return ans;
}

public static void solve() throws Exception{
    InputStreamReader ip=new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(ip);
    int t = Integer.parseInt(br.readLine());
   
   while(t-->0){
    int n =Integer.parseInt(br.readLine());
    String[] strs=(br.readLine()).trim().split(" ");
    // int n=Integer.parseInt(strs[0]),l=Integer.parseInt(strs[1]),r=Integer.parseInt(strs[2]),s=Integer.parseInt(strs[3]);
    //  String str=(br.readLine()).trim();
        int[] arr=new int[n];

        for(int i=0;i<n;i++){
            arr[i]=Integer.parseInt(strs[i]);
        }

        // sort(arr);

        int[] pre=new int[n];
        int[] suf=new int[n];

        pre[0]=arr[0];  suf[n-1]=arr[n-1];

        for(int i=1;i<n;i++){
            pre[i]=(arr[i] & pre[i-1]);
        }

        for(int i=n-2;i>=0;i--){
            suf[i]=(suf[i+1] & arr[i]);
        }

        HashMap<Integer,Integer> hm=new HashMap<>();
        for(int i=0;i<n;i++){
            hm.put(arr[i], hm.getOrDefault(arr[i], 0)+1);
        }

        HashMap<Integer,Integer> shm=new HashMap<>();
        // ArrayList<Integer> list=new 

        long ans=0;
        // long ct=1;

        for(int i=0;i<n-1;i++){
            shm.put(arr[i], shm.getOrDefault(arr[i], 0)+1);
            // if(i>0 && arr[i]==arr[i-1]){
            //     ct++;
            // }else{ct=1;}

            if(pre[i]==suf[i+1]){
                System.out.println(i+"  "+pre[i]+"  "+suf[i+1]);
                 long f1=fact(i+1);
                 long f2=fact(n-(i+1));
                

                //  for(int key:hm.keySet()){
                //      long fq=hm.get(key);
                //      long ct=shm.getOrDefault(key, 0);

                //      f1=f1/fact(ct);
                //     f2=f2/fact(fq-ct);
                //     //  if(key<arr[i]){
                //     //      f1=f1/fact(fq);
                //     //  }else if(key>arr[i]){
                //     //     f2=f2/fact(fq-ct);
                //     // }else{
                //     //     f1=f1/fact(ct);
                //     //     f2=f2/fact(fq-ct);
                //     // }
                //  }

                 ans=(ans+(f1*f2)%mod)%mod;  // ans=(ans+f2)%mod;  
                 System.out.println(ans);
            }

        }

        System.out.println(ans);
   }
}

//******************************************************************************************************************** */
    public static void main(String[] args) throws Exception{
        solve2();
     }

     public static void solve2() throws Exception{
        InputStreamReader ip=new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(ip);
        int t = Integer.parseInt(br.readLine());
        
        long[] arr=new long[200500];

        for(int i=0;i<10;i++){arr[i]=1;}

        for(int i=10;i<200500;i++){
            arr[i]=arr[i-10]+arr[i-9];  arr[i]=arr[i]%mod;
        }
        
        StringBuilder sb=new StringBuilder();

       while(t-->0){
       
        // int n =Integer.parseInt(br.readLine());
        String[] strs=(br.readLine()).trim().split(" ");
        // int n=Integer.parseInt(strs[0]),l=Integer.parseInt(strs[1]),r=Integer.parseInt(strs[2]),s=Integer.parseInt(strs[3]);
         String st=(strs[0]).trim();
         long m=Long.parseLong(strs[1]);
            long ans=0;

            char[] str=st.toCharArray();

            for(char ch:str){
                long tt=ch-'0';
                ans=ans+arr[(int)(tt+m)];
                ans+=mod;
                ans%=mod;
            }
            sb.append(ans);
            sb.append("\n");
            // System.out.println(ans);
        }

        System.out.println(sb);
    }
    //sort
     public static void sort(long[] arr) {
		int n = arr.length;
		for (int i = 0; i < n; i++) {
			int idx = (int) Math.random() * n;
			long temp = arr[i];  arr[i] = arr[idx];  arr[idx] = temp;  //swap
		}
		Arrays.sort(arr);
	}
 
	public static void sort(int[] arr) {
		int n = arr.length;
		for (int i = 0; i < n; i++) {
			int idx = (int) Math.random() * n;
			int temp = arr[i];  arr[i] = arr[idx]; arr[idx] = temp;  //swap
		}
		Arrays.sort(arr);
	}
    //1d print
    public static void print(int[] dp) {
		for (int val : dp) {
			System.out.print(val + " ");
		}
		System.out.println();
	}
 
	public static void print(long[] dp) {
		for (long val : dp) {
			System.out.print(val + " ");
		}
		System.out.println();
	}  
    //2d print
	public static void print(long[][] dp) {
		for (long[] a : dp) {
			for (long val : a) {
				System.out.print(val + " ");
			}
			System.out.println();
		}
	}
 
	public static void print(int[][] dp) {
		for (int[] a : dp) {
			for (int val : a) {
				System.out.print(val + " ");
			}
			System.out.println();
		}
	}
 
	
}
