t=int(input())
b={}
def ossa(g1):
    st,pr=[True]*(g1+1),[]
    for x in range(2,g1//2+1):
        if st[x]:
            pr.append(x)
            if g1%x==0:
                return x
        for y in pr:
            if x*y>g1:
                break
            st[x*y]=False
            if x%y==0:
                break
    return g1
for _ in range(t):
    m=int(input())
    if m in b:
        print(b[m])
        continue
    to,n,k=[],m,0
    while m!=1:
        j=m
        j=ossa(m)
        k^=j
        m=m//j
    b[n]=k
    print(k)