n = int(input())

for i in range(n):
    x = int(input())
    for j in range(2,x//2 + 1):
        if x % j == 0 :
            print(x,0)
            break
        if j == x // 2:
            print(x,1)