def solve_tc():
    n, m = map(str, input().split())
    m = int(m)
    n = list(n)
    for i in range(len(n)):
        n[i] = int(n[i])
    d = {}
    nd = {}
    cnt = 0
    for i in range(10):
        d[i] = 0
    for i in n:
        d[i] = d[i] + 1
    for j in range(m//10):
        nd[0] = d[9] + d[0]
        nd[1] = d[9] + d[1] + d[0]
        nd[2] = d[1] + d[2]
        nd[3] = d[2] + d[3]
        nd[4] = d[3] + d[4]
        nd[5] = d[4] + d[5]
        nd[6] = d[5] + d[6]
        nd[7] = d[6] + d[7]
        nd[8] = d[7] + d[8]
        nd[9] = d[8] + d[9]
        d = dict(nd)
        print(d)

    for j in range(int(m % 10)):
        nines = d[9]
        for i in [8, 7, 6, 5, 4, 3, 2, 1, 0]:
            d[i + 1] = d[i]
        d[0] = nines
        d[1] = d[1] + nines
    for i in d:
        cnt += int(d[i] % (10e9+7))
    return cnt


t = int(input())
while t > 0:
    t -= 1
    print(solve_tc())