from math import lcm
from collections import deque

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
    PL = []
    for i in range(N + 1):
        if P[i] == 1:
            PL.append(i)
    return PL

maxn = 10 ** 9
PL = PrimeList(int(maxn**0.5) + 1)
PL = set(PL)
from collections import defaultdict

def factorization(x):
    dic = defaultdict(int)
    for p in PL:
        if x in PL:
            dic[x] = 1
            return dic
        while x % p == 0:
            dic[p] += 1
            x //= p
        if x == 1:
            return dic
    dic[x] = 1
    return dic


# 約数の数
def N_divisors(x):
    dic = factorization(x)
    ret = 1
    for v in dic.values():
        ret *= (v+1)
    return ret

# 素因数の数
def n_factorization(x):
    cnt = 0
    for p in PL:
        if x in PL:
            cnt += 1
            return cnt
        while x % p == 0:
            cnt += 1
            x //= p
        if x == 1:
            return cnt
    # ここには来ないはず
    print("factorization error")
    return "error"

def divisors(PF):
    D = deque([1])
    for k, v in PF.items():
        D2 = deque()
        while D:
            x = D.pop()
            for i in range(v + 1):
                D2.append(x * pow(k, i))
        D = D2
    return sorted(list(D))

for _ in range(int(input())):
    N = int(input())
    dic = factorization(N)
    ans = 1
    for k in dic.keys():
        if k in [2,3,5]:
            continue
        D = divisors(factorization(k-1))
        for d in D:
            if pow(10,d,N) == 1:
                break
        ans = lcm(ans,d)
    print(ans)