def read_ints():
    return [int(i) for i in input().split()]

def new_digits(digits):
    ret = [0 for i in range(10)]
    for i in range(10):
        ret[(i+1) % 10] = digits[i]
    ret[1] = (ret[1] + digits[9]) % (10 ** 9 + 7)
    return ret


def solve(n, m):
    digits = [0 for i in range(10)]
    for c in str(n):
        digits[int(c)] += 1

    for i in range(m):
        digits = new_digits(digits)
    return sum(digits)

T = int(input())
for t in range(1, T+1):
    nums = read_ints()
    answer = solve(nums[0], nums[1])
    print('Case #{0}: {1}'.format(t, answer))
