import random import math def judge_miller(val): if(val == 1): return False if(val == 2): return True if(val % 2 == 0): return False for k in range(100): a = random.randint(2, val-1) if(math.gcd(a, val) != 1): return False x = val - 1 is_prime = False while(x % 2 == 0): m = pow(a, x, val) if(m % val == val-1): is_prime = True x = int(x/2) m = pow(a, x, val) if(m % val == 1 or m % val != val-1): is_prime = True if(is_prime): return True return False 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")