import random import math def judge_miller(val): if(val == 1): return False if(val == 2): return True if(val % 2 == 0): return False d = val - 1 while(d & 1 == 0): d >>= 1 for k in range(100): a = random.randint(2, val - 1) may_prime = False x = pow(a, d, val) if(x == 1): may_prime = True while((not may_prime) and x != val - 1 and d != val - 1): if(x == val - 1): may_prime = True d <<= 1 x = (x * x) % val if(x == val - 1): may_prime = True if(not may_prime): return False return True if __name__ == "__main__": x = int(input()) for i in range(x): v = int(input()) res = judge_miller(v) if(res): print(str(v)+" 1") else: print(str(v)+" 0")