C. Add One--Divide by Zero 2021 and Codeforces Round ＃714 (Div. 2)

Divide by Zero 2021 and Codeforces Round #714 (Div. 2)

C. Add One

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an integer nn. You have to apply mm operations to it.

In a single operation, you must replace every digit dd of the number with the decimal representation of integer d+1d+1. For example, 19121912 becomes 2102321023 after applying the operation once.

You have to find the length of nn after applying mm operations. Since the answer can be very large, print it modulo 109+7109+7.

Input

The first line contains a single integer tt (1≤t≤2⋅1051≤t≤2⋅105) — the number of test cases.

The only line of each test case contains two integers nn (1≤n≤1091≤n≤109) and mm (1≤m≤2⋅1051≤m≤2⋅105) — the initial number and the number of operations.

Output

For each test case output the length of the resulting number modulo 109+7109+7.

Example

input

Copy

5
1912 1
5 6
999 1
88 2
12 100

output

Copy

5
2
6
4
2115

Note

For the first test, 19121912 becomes 2102321023 after 11 operation which is of length 55.

For the second test, 55 becomes 2121 after 66 operations which is of length 22.

For the third test, 999999 becomes 101010101010 after 11 operation which is of length 66.

For the fourth test, 8888 becomes 10101010 after 22 operations which is of length 44.

=========================================================================

For each number, the effect of a fixed number of operations is also fixed , So we can preprocess every digital operation m Length of times . dp[i][j] For operation i Time ,j The length obtained by numbers , General 0-8, operation i The length obtained at a time is j+1, operation i-1 Length obtained for times , And for 9 Come on , yes i-1 Time , get 0,1 The sum of the lengths .

# include<iostream>
# define mod 1000000007
using namespace std;

typedef long long int ll;

ll dp[200000+10][10];

int main ()
{

  for(int i=0;i<=9;i++)
  {
      dp[0][i]=1;
  }
  for(int i=1;i<=200000;i++)
  {
      for(int j=0;j<9;j++)
      {

         dp[i][j]=dp[i-1][j+1];

      }

      dp[i][9]=(dp[i-1][0]+dp[i-1][1])%mod;


  }

  int t;

  cin>>t;
  while(t--)
  {

     ll n,m;
     
     scanf("%lld%lld",&n,&m);
     
     
      while(n)
      {
          ans=(ans+dp[m][n%10])%mod;

          n/=10;
      }

      cout<<ans<<'\n';

  }
    return 0;

}