# 解説を読んだ。
# 賢すぎて全く思いつける気がしないが……。

MAX=100003

X=[i*i+1 for i in range(MAX)]
ANS=[[] for i in range(MAX)]

for i in range(1,MAX):
    if X[i]==1:
        continue
    else:
        p=X[i]
        k=i%p

        for j in range(k,MAX,p):
            while X[j]%p==0:
                ANS[j].append(p)
                X[j]//=p

        k=(-i)%p

        for j in range(k,MAX,p):
            while X[j]%p==0:
                ANS[j].append(p)
                X[j]//=p

Q=int(input())
for i in range(Q):
    x=int(input())
    print(*ANS[x])