import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	void run() throws Exception {
		int cnt_tests = nextInt();
		for (int test = 0; test < cnt_tests; test++) {
			solve();
		}
	}

	long mod = 1000_000_007;
	
	static long matrix [][] = new long[10][10];
	static {
		for(int i = 0; i < 10; i++)
			matrix[(i + 9) % 10][i] = 1;
		matrix[9][1] = 1;
	}
	
	long mul(long a, long b) {
		return (a * b) % mod;
	}
	long sum(long a, long b) {
		return (a + b) % mod;
	}
	
	void mul(long m1[][], long m2[][], long to[][]) {
		int n = m1.length;
		int m = m2[0].length;
		int t = m1[0].length;
		for (int i = 0; i < n; i++) {
		  for (int j = 0; j < m; j++) {
			  to[i][j] = 0;
			  for (int k = 0; k < t; k++) {
				  to[i][j] = sum(to[i][j], mul(m1[i][k], m2[k][j]));  
			  }
		  }
	  }
	}
	
	long matrix_sum(long m[][]) {
		long ret = 0;
		for(long[] x : m) {
			for(long xx : x) {
				ret = sum(ret, xx);
			}
		}
		return ret;
	}
	
	static long bin_pow_cache[][][] = new long[40][][];
	static long spare[][] = new long[10][10];
	
	long[][] bin_pow(long m[][], int pow) {
		long result[][] = new long[m.length][m.length];
		for(int i = 0; i < m.length; i++) {
			result[i][i] = 1;
		}
		if (bin_pow_cache[1] == null) {
			bin_pow_cache[1] = new long[m.length][m.length];
		  mul(result, m, bin_pow_cache[1]);
		}

		
		
		int deg = 0;
		while(pow > 0) {
			deg++;
			if ((pow & 1) != 0) {
				mul(result, bin_pow_cache[deg], spare);
				long[][] tmp = spare; spare = result; result = tmp;
			}
			if(bin_pow_cache[deg+1] == null) {
			  bin_pow_cache[deg+1] = new long[10][10];
			  mul(bin_pow_cache[deg], bin_pow_cache[deg], bin_pow_cache[deg+1]);
			}
			pow >>= 1;
		}
		return result;
	}
	

	long cnt[][]    = new long[1][10];
	long result[][] = new long[1][10];
	
	private void solve() throws IOException {
		int n = nextInt();
		int m = nextInt();

		String str = Integer.valueOf(n).toString();
		for(char ch : str.toCharArray()) {
			cnt[0][ch - '0']++;
		}

		mul(cnt, bin_pow(matrix, m), result);
		long len = 0;
		for(long val : result[0]) {
			len = sum(len, val);
		}
		System.out.println(len);
		
	}

	public static void main(String[] args) throws Exception {
		Main instance = new Main();
		instance.initStreams();
		instance.run();
		instance.closeStreams();
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");

	void initStreams() throws FileNotFoundException {
		if (new File("input.txt").exists()) {
			try {
				System.setIn(new FileInputStream("input.txt"));
			} catch (FileNotFoundException e1) {
				e1.printStackTrace();
			}
		}
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
	}

	void closeStreams() throws IOException {
		in.close();
		out.close();
	}

	String nextString() throws IOException {
		while (!st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextString());
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextString());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextString());
	}
}
