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.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;



#define MAX 1000000007
#define vi vector<int>
#define vl vector<long long>
#define pi pair<int,int>
#define pl pair<long long,long long>
#define pb push_back
#define mi map<int,int>
#define ml map<long long,long long>

ll dp[10][200001];
ll a[10];
ll b[10];

void makedp()
{
    ll i,j,ii,sz=0;
    for(i=0;i<10;i++)
    {
        dp[i][0]=1;

    }
    for(i=0;i<10;i++)
    {
        sz=1;
        for(j=0;j<10;j++){a[j]=0;b[j]=0;}
        a[i]=1;
        for(j=1;j<=200000;j++)
        {
          for(ii=0;ii<10;ii++)
          {
           if(ii==9)
           {
               sz+=a[ii];b[0]+=a[ii];b[1]+=a[ii];a[ii]=0;

           }
           else
           {
               b[ii+1]+=a[ii];a[ii]=0;
           }
          }
          dp[i][j]=sz;
          for(ii=0;ii<10;ii++)
          {
              a[ii]=b[ii];
              a[ii]=a[ii]%MAX;
              b[ii]=0;
          }

        }
    }
   // for(i=0;i<=20;i++)
   // {
   //     cout<<dp[1][i]<<" ";
   // }
   // printf("\n");

}
int main()
{
    makedp();
    int t;scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d %d",&n,&m);
        ll s=0;
        while(n)
        {
          //cout<<dp[n%10][m]<<" ";
          s+=dp[n%10][m];
          s=s%MAX;
          n/=10;
        }
        printf("%lld\n",s%MAX);

    }
    return 0;
}
