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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

import static java.lang.System.currentTimeMillis;

public class JCAddOne {
    public static void main(String[] args) throws IOException {
//        long start = currentTimeMillis();
        BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
//        BufferedReader file = new BufferedReader(new InputStreamReader(new ByteArrayInputStream(
//        "5\n1912 1\n5 6\n999 1\n88 2\n12 100".getBytes())));
//        "1\n12 100".getBytes())));
        PrintWriter out = new PrintWriter(System.out);
        int t = Integer.parseInt(file.readLine());
        int modulo = (int) 1e9 + 7;
        long[] cache = new long[200011];

        for (int i = 0; i < 10; i++) cache[i] = 1L;
        for (int i = 10; i <= 200010; i++) cache[i] = (cache[i - 9] + cache[i - 10]) % modulo;

        while (t-- > 0) {
            String[] a = file.readLine().split(" ");
            int ab = Integer.parseInt(a[0]);
            int b = Integer.parseInt(a[1]);
            var ints = ab;
            var sum = 0L;
            while (ints > 0) {
                int i = ints % 10;
                sum = (sum + cache[b + i]) % modulo;
                ints /= 10;
            }
            out.println(sum);
        }
//        out.println(currentTimeMillis() - start);
        out.close();
    }
}
