using System; using System.Collections.Generic; using System.Linq; using static System.Console; using static System.Math; class Program { static void Main() { var n = long.Parse(ReadLine()); for (int i = 0; i < n; i++) { var x = long.Parse(ReadLine()); WriteLine(x.ToString() + " " + (MillerRabin(x) ? "1" : "0")); } } static int[] l = new int[] { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 }; static bool MillerRabin(long n) { if (n < 2) return false; if (n % 2 == 0) return n == 2; var d = n - 1; var s = 0; while (d % 2 == 0) { s++; d >>= 1; } for (int i = 0; i < l.Length && l[i] < n; i++) { var a = l[i]; var c = true; var x = System.Numerics.BigInteger.ModPow(a, d, n); if (x == 1) c = false; for (int r = 0; r < s; r++) { if (x == n - 1) c = false; x = x * x % n; } if (c) return false; } return true; } }