Case = int(input())
for _ in range(Case):
    N = int(input())
    while N%2 == 0:
        N //= 2
    while N%5 == 0:
        N //= 5
    ans = 1
    base = 9; keta = 1
    while base%N != 0:# and ans < 100:
        base %= N
        keta *= 10; keta %= N
        base += keta*9
        ans += 1
        #print(base,ans)
    print(ans)