from itertools import combinations
from math import prod

def PrimeList(N):
    P = [1] * (N + 1)
    P[0] = P[1] = 0
    for i in range(2, N + 1):
        if P[i]:
            for j in range(i + i, N + 1, i):
                P[j] = 0
    for i in range(N + 1):
        if P[i] == 1:
            PL.append(i)

maxn = 10 ** 9
maxn2 = int(maxn**0.5) + 1

PL = []
PrimeList(maxn2)

from collections import defaultdict

def factors(x):
    F = []
    for p in PL:
        if x % p == 0:
            F.append(p)
            while x % p == 0:
                x //= p
        if x == 1:
            return F
    F.append(x)
    return F

def euler_function(x):
    F = factors(x)
    NF = len(F)
    x0 = x
    for i in range(1,NF+1):
        for fs in combinations(F,i):
            x += x0 // prod(fs) * (-1) ** i
    return x

def solve(N):
    x = euler_function(N)

def make_divisors(n):
    divisors = []  #必要に応じてsetにしても良いかも
    i = 1
    while i ** 2 <= n:
        if n % i == 0:
            divisors.append(i)
            if i ** 2 != n:
                divisors.append(n//i)
        i += 1
    divisors.sort()
    return divisors

for _ in range(int(input())):
    N = int(input())
    while N % 2==0:
        N //= 2
    while N % 5 == 0:
        N //= 5
    if N == 1:
        print(1)
        continue
    D = make_divisors(euler_function(N))
    for d in D:
        if pow(10,d,N) == 1:
            print(d)
            break