#include <bits/stdc++.h>

#define IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1e9 + 7;

template<typename T, typename U>
pair<T, U> operator+(const std::pair<T, U> &l, const std::pair<T, U> &r) {
    return {l.first + r.first, l.second + r.second};
}

template<typename T, typename U>
pair<T, U> operator-(const std::pair<T, U> &l, const std::pair<T, U> &r) {
    return {l.first - r.first, l.second - r.second};
}
const int N =2e5 + 10;
int dp[N][10];
int solve(int num , int m){
    if(dp[m][num]!=-1){
        return dp[m][num];
    }
    if(m==0){
        return 1;
    }
    num++;
    ll ans = 0;
    if(num==10){
        ans+=solve(1,m-1);
        ans+=solve(0,m-1);
        ans%=MOD;
    }else{
        ans=solve(num,m-1);
    }
    return dp[m][num-1] = ans;
}
int main() {
    IO;
    int t;
    cin>>t;
    memset(dp,-1,sizeof dp);
    while (t--){
        string str;
        cin>>str;
        int m ;
        cin>>m ;
        ll ans = 0 ;
        for(char ch : str){
            ans+=solve(ch-'0',m);
            ans%=MOD;
        }
        cout<<ans<<endl;

    }
}
### Prompt

Create a solution in cpp for the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>

#define IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1e9 + 7;

template<typename T, typename U>
pair<T, U> operator+(const std::pair<T, U> &l, const std::pair<T, U> &r) {
    return {l.first + r.first, l.second + r.second};
}

template<typename T, typename U>
pair<T, U> operator-(const std::pair<T, U> &l, const std::pair<T, U> &r) {
    return {l.first - r.first, l.second - r.second};
}
const int N =2e5 + 10;
int dp[N][10];
int solve(int num , int m){
    if(dp[m][num]!=-1){
        return dp[m][num];
    }
    if(m==0){
        return 1;
    }
    num++;
    ll ans = 0;
    if(num==10){
        ans+=solve(1,m-1);
        ans+=solve(0,m-1);
        ans%=MOD;
    }else{
        ans=solve(num,m-1);
    }
    return dp[m][num-1] = ans;
}
int main() {
    IO;
    int t;
    cin>>t;
    memset(dp,-1,sizeof dp);
    while (t--){
        string str;
        cin>>str;
        int m ;
        cin>>m ;
        ll ans = 0 ;
        for(char ch : str){
            ans+=solve(ch-'0',m);
            ans%=MOD;
        }
        cout<<ans<<endl;

    }
}
```