from math import sqrt
def PrimeFactorization(N):
    ret = []
    for i in range(2,int(sqrt(N))+1):
        while N % i == 0:
            ret.append(i)
            N //= i
    if N > 1:
        ret.append(N)
    return ret

def solve():
    N = int(input())
    ret = PrimeFactorization(N)
    M = len(ret)
    for bit in range(1<<M):
        b = bit
        x = 1
        for i in range(M):
            if b & 1:
                x *= ret[i]
            b >>= 1
        if int(str(N) + str(x)) % (N + x) == 0:
            print(x)
            return

T = int(input())
for _ in range(T):
    solve()