rown = int(input())
upMuls = []
codeNums = []
for count in range(0,rown):
    two = input().split(' ')
    upMuls.append(int(two[0]))
    codeNums.append(two[1])
def competedUpMul(n):
    result = 1
    for count in range(2,n + 1):
        result *= count
    return result
times = []
for i in range(0,rown):
    codes = str(competedUpMul(upMuls[i]))
    times.append(codes.count(codeNums[i]))
for i in range(0,rown):
    print(times[i])