def main(n,m):
    mod=10*9+7
    count=[0 for x in range(10)]
    z=n
    while z:
        digit=z%10
        z=z//10
        count[digit]=count[digit]+1
    hash=dict()
    for index in range(1,m+1):
        new=[0 for z in range(10)]
        new[2]=count[1]
        new[3]=count[2]
        new[4] = count[3]
        new[5] = count[4]
        new[6] = count[5]
        new[7] = count[6]
        new[8] = count[7]
        new[9] = count[8]
        new[0] = count[9]
        new[1] = (count[0] + count[9])
        s=0
        for i in range(10):
            count[i]=new[i]
            s=s+count[i]%mod
        hash[index]=s
    return hash[m]%mod
t=int(input())
for test in range(t):
    n,m=map(int,input().split())
    print(main(n,m))