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.lang.*;
import java.io.*;

public class Main
{
	PrintWriter out = new PrintWriter(System.out);
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tok = new StringTokenizer("");
    String next() throws IOException {
        if (!tok.hasMoreTokens()) { tok = new StringTokenizer(in.readLine()); }
        return tok.nextToken();
    }
    int ni() throws IOException { return Integer.parseInt(next()); }
    long nl() throws IOException { return Long.parseLong(next()); }
    
    long mod=1000000007;
    long[]D,E;
    
    void solve() throws IOException {
        D=new long[200001];
        E=new long[200001];
        for (int i=0;i<10;i++) D[i]=1;
        for (int i=0;i<9;i++) E[i]=1;
        E[9]=2;
        for (int i=10;i<200001;i++) {
            D[i]=(D[i-10]+E[i-10])%mod;
            E[i]=(E[i-9]+D[i-9])%mod;
        }
        
        for (int tc=ni();tc>0;tc--) {
            int n=ni(),m=ni();
            long ans=0;
            while (n>0) {
                int d=n%10;
                if (d==0) ans=(ans+D[m])%mod;
                if (d==1) ans=(ans+E[m])%mod;
                if (d>1) {
                    if (d+m<10) ans++;
                    else {
                        int left=(m-10+d);
                        ans=(ans+D[left]+E[left])%mod;
                    }
                }
                n/=10;
            }
            ans=ans%mod;
            out.println(ans);
        }
        out.flush();
    }

    int gcd(int a,int b) { return(b==0?a:gcd(b,a%b)); }
    long gcd(long a,long b) { return(b==0?a:gcd(b,a%b)); }
    long mp(long a,long p) { long r=1; while(p>0) { if ((p&1)==1) r=(r*a)%mod; p>>=1; a=(a*a)%mod; } return r; }
    
    public static void main(String[] args) throws IOException {
        new Main().solve();
    }
}