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;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define take ll a[n]; for(int i=0;i<n;i++){cin>>a[i];}
#define ll long long int
#define output for (int i=0;i<n;i++){cout<<a[i]<<' ';}cout<<endl;
#define vv vector<ll> 
#define VIN(a) for(auto &it:a) cin>>it;
#define pb push_back 
#define CIN(x,i,a,b) for(int i=a;i<b;i++){cin>>x[i];}
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define se(a) a.begin(),a.end()
#define ppi vector<pair <ll,ll>>
const int MAX_N = 1e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
#define Endl endl;
#define DP(n,w) int dp[n+1][w+1]; memset(dp, 0, sizeof(dp));
#define INIT int t[200005]; memset(t,-1,sizeof(t));
#define INITDP int t[200005][200005]; memset(t,-1,sizeof(t));
#define mem(a,x) memset(a,x,sizeof(a));
ll dp[200001];
void solve() 
{
      ll n,m;
      cin>>n>>m;
      
      
      ll ans=0;
      while(n>0)
      {
            ll x=n%10;
            if(x+m<10)
            {
                  ans+=1;
            }
            else
            {
                  ans+=dp[x+m-10];
            }
            ans%=MOD;
            n/=10;
      }
      cout<<ans<<endl;
}
int main() 
{
fast
for(int i=0;i<9;i++)
{
      dp[i]=2;
}
dp[9]=3;
for(int i=10;i<200001;i++)
{
      dp[i]=(dp[i-9]+dp[i-10])%MOD;
}
int q=1; cin >> q; while(q--){ solve();}
}