t=int(input())
for i in range(t):
    k=input()
    n=int(k[0])
    a=int(k[2])
    res=1;
    for i in range(1,n+1):
        res*=i;
    cnt=0
    while res>0:
        if (res%10==a):
            cnt+=1
        res//=10
    print(cnt)