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.
// package ProblemSolving.codeforces714;

import java.io.*;
import java.util.StringTokenizer;

public class C_Upsolving {
    static final int MAX = 200020;
    static long [][] dp = new long[10][MAX];    //dp[숫자][연산 몇번 적용] = 연산 적용 후 길이
    static final int q= (int)1e9+7;

    public static void precalc(){
        //0번 적용
        for(int i=0;i<=9;i++) dp[i][0]=1;
        //1번 적용
        for(int i=0;i<=8;i++) dp[i][1]=1;
        dp[9][1]=2;

        //2번 이상 적용:: j>=2
        // i<=8 -> dp[i][j] = dp[i+1][j-1]
        // i==9 -> dp[i][j] =dp[0][j-1] + dp[1][j-1]

        for(int j=2;j<MAX;j++){
            for(int i=0;i<=8;i++){
                dp[i][j] =dp[i+1][j-1]; //톱니바퀴 처럼 맞물리는 완벽한 논리네...
            }
            dp[9][j] =dp[0][j-1]+dp[1][j-1]; //톱니바퀴 처럼 맞물리는 완벽한 논리네...
            dp[9][j]%=q;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        precalc();

        int tc= Integer.parseInt(br.readLine());
        for(int tt=0;tt<tc;tt++){
            st = new StringTokenizer(br.readLine());
            int n= Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            String s= String.valueOf(n);
            long answer=0;

            for(int i=0;i<s.length();i++){
                char c= s.charAt(i);
                answer+=dp[c-'0'][m];
                answer%=q;
            }

            //System.out.println(answer);
            bw.write(String.valueOf(answer)+"\n");
        }
        bw.flush();
        bw.close();
    }

}
