def miller_rabin(n, bases): d, s = n - 1, 0 while d % 2 == 0: d >>= 1 s += 1 for a in bases: if n <= a: return True a = pow(a, d, n) if a == 1: continue r = 1 while a != n - 1: if r == s: return False a = a * a % n r += 1 return True def is_prime1(n): # < 4759123141 return miller_rabin(n, [2, 7, 61]) def is_prime2(n): # < 2 ** 64 return miller_rabin(n, [2, 3, 5, 7, 325, 9375, 28178, 450775, 9780504, 1795265022]) def is_prime(n): """ https://miller-rabin.appspot.com/ """ if n < 4759123141: return is_prime1(n) else: return is_prime2(n) for i in range(int(input())): x = int(input()) print(x, int(is_prime(x)))