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.
from __future__ import division
from sys import stdin, stdout


def fast2():
    import os, sys, atexit
    from cStringIO import StringIO as BytesIO
    # range = xrange
    sys.stdout = BytesIO()
    atexit.register(lambda: os.write(1, sys.stdout.getvalue()))
    return BytesIO(os.read(0, os.fstat(0).st_size)).readline


input = fast2()
rint = lambda: int(stdin.readline())
rints = lambda: [int(x) for x in input().split()]
pr = lambda args, sep: stdout.write(sep.join(map(str, args)) + '\n')
ceil1, out = lambda a, b: (a + b - 1) // b, []

mem = [0] * 10
mem[9], mem2, mod = 1, [1], 10 ** 9 + 7

for i in range(2 * 10 ** 5):
    new = [0] * 10
    for j in range(9):
        new[j + 1] = mem[j]

    new[0] = (mem[9] + new[0]) % mod
    new[1] = (mem[9] + new[1]) % mod

    mem = new
    mem2.append(sum(mem) % mod)

for _ in range(int(input())):
    ans = 0
    n, m = rints()
    for i in str(n):
        if i == '9':
            ans = (ans + mem2[m]) % mod
        elif m - (9 - int(i)) <= 0:
            ans = (ans + 1) % mod
        else:
            ans = (ans + mem2[m - (9 - int(i))]) % mod

    out.append(ans)

pr(out, '\n')
