a=int(input())
for i in range(a):
    x=list(map(int,input().split()))
    b=x[0]
    c=0
    for j in range(1,x[0]+1):
        b*=j
    b=str(b)
    for j in range(0,len(b)):
        if b[j]==b[1]:
            c+=1
    print(c)