n = int(input())

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