import math
import random

def jacobi_symbol(a, n):
  if n < 0 or not n % 2:
    raise ValueError("n should be an odd positive integer")
  if a < 0 or a > n:
    a = a % n
  if n == 1 or a == 1:
    return 1
  if math.gcd(a, n) != 1:
    return 0
  j = 1
  if a < 0:
    a = -a
    if n % 4 == 3:
      j = -j
  while a != 0:
    while a % 2 == 0 and a > 0:
      a >>= 1
      if n % 8 in (3, 5):
        j = -j
    a, n = n, a
    if a % 4 == 3 and n % 4 == 3:
      j = -j
    a %= n
  if n != 1:
    j = 0
  return j

def solovay_strassen(n):
  if n == 2 or n == 3:
    return True
  if n % 2 == 0:
    return False
  for _ in range(40):
    a = random.randrange(1, n - 1)
    if math.gcd(a, n) > 1:
      return False
    j = jacobi_symbol(a, n)
    if j % n != pow(a, (n - 1) >> 1, n):
      return False
  return True

for i in range(int(input())):
  x = int(input())
  print(x, int(solovay_strassen(x)))