class INPUT:
  def __init__(self):
    from sys import argv
    if argv[-1] in ["./Main.py","prog.py","Main.py"]:#Atcoder:./Main.py,Wandbox:prog.py,yukicoder:Main.py
      self.l=open(0).read().split()[::-1]
    else:
      self.l=open("_input.txt",mode="r").read().split()[::-1]
    self.length=len(self.l)
    return

  def stream(self,k=1,f=int,f2=False):
    assert(-1<k)
    m=self.length
    if m==0 or m<k:
      raise Exception("There is no input!")
    elif f!=str:
      if k==0:
        self.length=0
        return list(map(f,self.l[::-1]))
      if k==1 and not f2:
        self.length-=1
        return f(self.l.pop())
      if k==1 and f2:
        self.length-=1
        return [f(self.l.pop())]
      ret=[]
      for _ in [0]*k:
        ret.append(f(self.l.pop()))
      self.length-=k
      return ret
    else:
      if k==0:
        self.length=0
        return self.l[::-1]
      if k==1 and not f2:
        self.length-=1
        return self.l.pop()
      if k==1 and f2:
        self.length-=1
        return [self.l.pop()]
      ret=[]
      for _ in [0]*k:
        ret.append(self.l.pop())
      self.length-=k
      return ret
pin=INPUT().stream

"""
pin(number[default:1],f[default:int],f2[default:False])
if number==0 -> return left all
eclipse 等では_input.txtを使うこと。
listを変数で受け取るとき、必ずlistをTrueにすること。
"""

#ACL
def is_prime(n):
  #assert(0<=n<=4294967296)
  if n in [2,7,61]:
    return 1
  if n<=1 or n%2==0:
    return 0
  d=n-1
  while d%2==0:
    d//=2
  for a in [2,7,61]:
    t=d
    y=pow(a,t,n)
    while t!=n-1 and y not in [1,n-1]:
      y=y*y%n
      t<<=1
    if y!=n-1 and t%2==0:
      return 0
  return 1

def main():
  n=pin(1)
  a=pin(0)
  for i in range(n):
    print(a[i],is_prime(a[i]))
  return

main()