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, math
import heapq

from collections import deque
input = sys.stdin.readline

#input
def ip(): return int(input())
def sp(): return str(input().rstrip())

def mip(): return map(int, input().split())
def mfp(): return map(float, input().split())
def msp(): return map(str, input().split())

def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split()))

#gcd, lcm
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def lcm(x, y):
    return x * y // gcd(x, y)

#prime
def isPrime(x):
    if x==1: return False
    for i in range(2, int(x**0.5)+1):
        if x%i==0:
            return False
    return True

# Union Find
# p = {i:i for i in range(1, n+1)}
def find(x):
    if x == p[x]:
        return x
    q = find(p[x])
    p[x] = q
    return q

def union(x, y):
    global n
    x = find(x)
    y = find(y)

    if x != y:
        p[y] = x

def getPow(a, x):
    ret =1
    while x:
        if x&1:
            ret = (ret*a) % MOD
        a = (a*a)%MOD
        x>>=1
    return ret

def getInv(x):
    return getPow(x, MOD-2)

############### Main! ###############

MOD = 10**9 + 7
dp = [0 for _ in range(202020)]
for i in range(9):
    dp[i]=2
dp[9]=3
for i in range(10,202020):
    dp[i] = (dp[i-9]+dp[i-10])%MOD

t = ip()
while t:
    ans=0
    t -= 1
    n,k = mip()

    while n:
        if k+n%10<10:
            ans += 1
        else:
            ans += dp[k + n%10 - 10]

        n//=10

    print(ans%MOD)

######## Priest W_NotFoundGD ########