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 <iostream>
#include <stdio.h>
using namespace std;
int main()
{
    long long t,n,sum[10],total[200001],temp,temp1,temp2,inf=1000000007,j,ans,formulation;
    long long i,m,xiao=200000;
    for(i=0; i<10; i++)
        sum[i]=0;
    sum[0]=1;
    sum[1]=1;
    total[0]=2;
    for(i=1; i<=xiao; i++)
    {
        temp=sum[8]%inf;
        sum[8]=sum[7]%inf;
        sum[7]=sum[6]%inf;
        sum[6]=sum[5]%inf;
        sum[5]=sum[4]%inf;
        sum[4]=sum[3]%inf;
        sum[3]=sum[2]%inf;
        sum[2]=sum[1]%inf;
        sum[1]=sum[0]%inf+sum[9]%inf;
        sum[0]=sum[9]%inf;
        sum[9]=temp;
        total[i]=(sum[0]+sum[1]+sum[2]+sum[3]+sum[4]+sum[5]+sum[6]+sum[7]+sum[8]+sum[9])%inf;
    }
    scanf("%lld",&t);
    for(j=0; j<t; j++)
    {
        ans=0;
        scanf("%lld%lld",&n,&m);
        while(n!=0)
        {
            formulation=m+n%10-10;
            if(formulation<0)
                ans=(ans+1)%inf;
            else
            {
                ans=(ans+total[formulation])%inf;
            }
            n=n/10;
        }
        printf("%d\n",ans%inf);
    }
    return 0;
}
