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.*;
public class B{
	static long mod = (long)(1e9+7);
	static long[][] dp;
	
	static long make(int dig, int moves)
	{
		if(moves<=0)return 1;
		if(dp[dig][moves]!=0)return dp[dig][moves];
		long ans = 0;
		if(dig<9)
		{
			ans = make(dig+1,moves-1);
		}
		else
		{
			ans = (make(0,moves-1)%mod+make(1,moves-1)%mod)%mod;
		}
		dp[dig][moves] = ans;
		return ans%mod;
	}
	
	public static void main(String[] args)
	{
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		dp = new long[10][200005];
//		for(int i=0;i<10;i++)for(int j=0;j<200005;j++)dp[i][j] = -1;
		for(int i=0;i<10;i++)for(int j=0;j<200005;j++)dp[i][j] = make(i,j);
		int t = fs.nextInt();
		for(int tt=0;tt<t;tt++)
		{
			String str = fs.next(); int moves = fs.nextInt();
			long ans = 0;
			for(int i=0;i<str.length();i++)
			{
				int num = str.charAt(i)-'0';
				ans = (ans+dp[num][moves])%mod;
			}
			out.println(ans);
		}
		out.close();
	}
	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) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	public static int[] sort(int[] arr)
	{
		List<Integer> temp = new ArrayList();
		for(int i:arr)temp.add(i);
		Collections.sort(temp);
		int start = 0;
		for(int i:temp)arr[start++]=i;
		return arr;
	}
}