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 {

	static long mod = (long) (1e9 + 7);

	public static void main(String[] args) throws IOException {
		Scanner scn = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		StringBuilder sb = new StringBuilder();
		long dp[][] = new long[(int) (2e5 + 5)][10];
		int mx = dp.length;
		Arrays.fill(dp[0], 1);
		for (int i = 0; i < 10; i++) {
			int d[] = new int[10];
			d[i] = 1;
			int idx = 1;
			while (idx < mx) {
				int nd[] = new int[10];
				for (int g = 0; g < 9; g++)
					nd[g + 1] = d[g];
				if (d[9] != 0) {
					nd[0] += d[9];
					nd[1] += d[9];
					nd[0] %= mod;
					nd[1] %= mod;
				}
				long cnt = 0;
				for (long v : nd) {
					cnt += v;
					cnt %= mod;
				}
				dp[idx][i] = cnt;
				d = nd;
				idx++;
			}
		}
		int T = scn.ni(), tcs = 0;
		C: while (tcs++ < T) {
			int n = scn.ni();
			int m = scn.ni();
			int d[] = new int[10];
			while (n != 0) {
				d[n % 10]++;
				n /= 10;
			}
			int mod = (int) (1e9 + 7);
			long ans = 0;
			for (int i = 0; i < 10; i++) {
				if (d[i] == 0)
					continue;
				long p = d[i] * dp[m][i];
				p %= mod;
				ans += p;
				ans %= mod;
			}
			sb.append(ans);
			sb.append("\n");
		}
		out.print(sb);
		out.close();
	}

	static class Scanner {

		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int ni() throws IOException {
			return Integer.parseInt(next());
		}

		public long nl() throws IOException {
			return Long.parseLong(next());
		}

		public int[] nia(int n) throws IOException {
			int a[] = new int[n];
			String sa[] = br.readLine().split(" ");
			for (int i = 0; i < n; i++)
				a[i] = Integer.parseInt(sa[i]);
			return a;
		}

		public long[] nla(int n) throws IOException {
			long a[] = new long[n];
			String sa[] = br.readLine().split(" ");
			for (int i = 0; i < n; i++)
				a[i] = Long.parseLong(sa[i]);
			return a;
		}

		public void sort(int[] a) {
			ArrayList<Integer> l = new ArrayList<>();
			for (int v : a)
				l.add(v);
			Collections.sort(l);
			for (int i = 0; i < a.length; i++)
				a[i] = l.get(i);
		}

		public void sort(long[] a) {
			ArrayList<Long> l = new ArrayList<>();
			for (long v : a)
				l.add(v);
			Collections.sort(l);
			for (int i = 0; i < a.length; i++)
				a[i] = l.get(i);
		}
	}
}