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.
import sys
input=sys.stdin.readline

d=[0 for x in range(200001)]
d[0]=1
for i in range(1,10):
    d[i]=2
for i in range(10,200001):
    d[i]=(d[i-10]+d[i-9])%(10**9+7)
 
t =int(input())
 
for i in range(t):
    #n=int(input())
    n,m=map(int,input().split())
    #a=[int(x) for x in input().split()]
 
    n=list(str(n))
    count=[0 for x in range(10)]
    for i in n:
        count[int(i)]+=1
 
#    for i in range(m):
 #       temp=False
  #      temp1=count[9]
   #     if count[9]>0:
    #        temp=True
     #   for j in range(9,0,-1):
      #      count[j]=count[j-1]
       # count[0]=0
        #if temp:
         #   count[0]+=temp1
          #  count[1]+=temp1
 
    ans=0
    for i in range(10):
        temp=m-(9-i)
        if temp>0:
            ans+=d[temp]*count[i]
        else:
            ans+=count[i]
    print(ans%(10**9+7))