def baby_step_giant_step(a,b,mod):
    a %= mod
    b %= mod
    l = int(mod**0.5)+1
    h = 1 if mod != 0 else 0
    dic = {}
    for i in range(l):
        if h == b and i != 0:
            return i
        dic[h*b%mod] = i
        h *= a
        h %= mod
    g = h
    for i in range(l):
        if g in dic:
            res = (i+1)*l-dic[g]
            if pow(a,res,mod) == b:
                return res
            else:
                return -1
        g *= h
        g %= mod
    return -1

t = int(input())
for _ in range(t):
    n = int(input())
    while n%2 == 0:
        n //= 2
    while n%5 == 0:
        n //= 5
    print(baby_step_giant_step(10,1,n))