from sys import stdin,stdout
input=stdin.readline


def D():
    n=int(input())
    x=0
    y=1
    for _ in range(n*n):
        a=int(input())
        b=[]
        if x < n*n and y < n*n:
            if a == 1:
                b=[2,y//n+1,y%n+1]
                y += 2
            else:
                b=[1,x//n+1,x%n+1]
                x += 2
        elif x >= n*n:
            if a == 2:
                b=[3,y//n+1,y%n+1]
            else:
                b=[2,y//n+1,y%n+1]
            y+=2
        elif y >= n*n:
            if a == 1:
                b=[3,x//n+1,x%n+1]
            else:
                b=[1,x//n+1,x%n+1]
            x+=2

        if n % 2 == 0:
            if b[1] % 2 == 1:
                b[2] = n - b[2] + 1
        for i in b:
            stdout.write(str(i) + ' ')
        stdout.write('\n')
        stdout.flush()

def E():
    n=int(input())
    m=[0]*n
    for i in range(n):
        m[i]=list(map(int,input().split()))
    m.sort()
    cost=sum([m[i][1] for i in range(n)])
    latest=0
    for i in range(1,n):
        saved = max(m[i][0]-m[latest][0],m[i][1]) - m[i][1]
        if saved > 0:
            cost -= saved
            latest = i
    print(cost)

def D2():
    t=int(input())
    for _ in range(t):
        n,p=map(int,input().split())
        a=sorted(list(map(int,input().split())))
        w=p*(n-1)
        s=0
        for i in range(n-1):
            if a[i+1]%a[s] == 0:
                if a[s] < p:
                    w -= (p - a[s])
            else:
                s=i+1
        print(w)



def G():
    m=5*10**6
    p=list(range(m+1))
    b=[1]*(m+1)
    a=[-1]*(m+1)
    
    for i in range(2,m+1):
        if p[i]==i:
            p[i]=1
            b[i]=i+1
            for j in range(i*i,m+1,i):
                x=1
                p[j] //= i
                while p[j] % i == 0:
                    p[j] //= i
                    x += 1
                b[j] *= (1 - pow(i,x+1))//(1-i)
        if b[i] < m and a[b[i]] == -1:
            a[b[i]] = i
    
    t=int(input())
    for _ in range(t):
        print(a[int(input())])


#1 2 3 2*3

#2*(2+3
#1 2 3 2*2 2*3 2*2*3

G()
