using System; using System.Collections.Generic; using System.Linq; using static System.Console; using static System.Math; class Program { static void Main() { SetOut(new System.IO.StreamWriter(OpenStandardOutput()) { AutoFlush = false }); var n = FastIO.Long(); for (int i = 0; i < n; i++) { var x = (ulong)FastIO.Long(); WriteLine(x.ToString() + " " + (MillerRabin(x) ? "1" : "0")); } Out.Flush(); } public static uint[] b64 = new uint[] { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 }; public static bool MillerRabin(ulong n) { if (n == 2 || n == 3 || n == 5 || n == 7) return true; if ((n & 1) == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) return false; if (n < 121) return n > 1; var d = n - 1; var s = TrailingZeroCount(d); d >>= s; foreach (var a in b64) { if (a >= n) continue; var x = ModPow(a, d, n); if (x == 1) continue; for (int r = 0; r < s; r++) { if (x == n - 1) goto b; x = ModMul(x, x, n); } return false; b:; } return true; } static ulong BigMul(ulong a, ulong b, out ulong low) { uint al = (uint)a; uint ah = (uint)(a >> 32); uint bl = (uint)b; uint bh = (uint)(b >> 32); ulong mull = ((ulong)al) * bl; ulong t = ((ulong)ah) * bl + (mull >> 32); ulong tl = ((ulong)al) * bh + (uint)t; low = tl << 32 | (uint)mull; return ((ulong)ah) * bh + (t >> 32) + (tl >> 32); } static ulong ModPow(ulong x, ulong n, ulong m) { var res = 1ul; while (n != 0) { if ((n & 1) == 1) res = ModMul(res, x, m); x = ModMul(x, x, m); n >>= 1; } return res; } static ulong ModMul(ulong l, ulong r, ulong mod) { unchecked { if (mod <= uint.MaxValue) return l % mod * (r % mod) % mod; var high = BigMul(l, r, out var low) % mod; if (high == 0ul) return low % mod; var lzc = 0; if (0 <= (long)mod) { lzc = LeadingZeroCount(mod); mod <<= lzc; high = (high << lzc) | (low >> (64 - lzc)); low <<= lzc; } var mh = mod >> 32; var ml = (ulong)(uint)mod; var q = high / mh; var p = q * ml; high -= q * mh; high = (high << 32) | (low >> 32); if (high < p) { high += mod; if (high >= mod && high < p) { high += mod; } } high -= p; q = high / mh; p = q * ml; high -= q * mh; high = (high << 32) | (uint)low; if (high < p) { high += mod; if (high >= mod && high < p) { high += mod; } } return (high - p) >> lzc; } } public static int LeadingZeroCount(uint value) { if (value == 0) { return 32; } return 31 ^ Log2SoftwareFallback(value); } public static int LeadingZeroCount(ulong value) { uint hi = (uint)(value >> 32); if (hi == 0) { return 32 + LeadingZeroCount((uint)value); } return LeadingZeroCount(hi); } private static int Log2SoftwareFallback(uint value) { value |= value >> 01; value |= value >> 02; value |= value >> 04; value |= value >> 08; value |= value >> 16; return Log2DeBruijn[(int)((value * 0x07C4ACDDu) >> 27)]; } public static int TrailingZeroCount(uint value) { if (value == 0) { return 32; } return TrailingZeroCountDeBruijn[(int)(((value & (uint)-(int)value) * 0x077CB531u) >> 27)]; } public static int TrailingZeroCount(ulong value) { uint lo = (uint)value; if (lo == 0) { return 32 + TrailingZeroCount((uint)(value >> 32)); } return TrailingZeroCount(lo); } private static ReadOnlySpan Log2DeBruijn => new byte[32] { 00, 09, 01, 10, 13, 21, 02, 29, 11, 14, 16, 18, 22, 25, 03, 30, 08, 12, 20, 28, 15, 17, 24, 07, 19, 27, 23, 06, 26, 05, 04, 31 }; private static ReadOnlySpan TrailingZeroCountDeBruijn => new byte[32] { 00, 01, 28, 02, 29, 14, 24, 03, 30, 22, 20, 15, 25, 17, 04, 08, 31, 27, 13, 23, 21, 19, 16, 07, 26, 12, 18, 06, 11, 05, 10, 09 }; } public static class FastIO { static System.IO.Stream str = System.Console.OpenStandardInput(); const int size = 1024; static byte[] buffer = new byte[size]; static int ptr = size; static byte Read() { if (ptr == size) { str.Read(buffer, 0, size); ptr = 0; } return buffer[ptr++]; } public static long Long() { var c = Read(); while (c < 0x21) { c = Read(); } var n = false; if (c == '-') { n = true; c = Read(); } var ret = 0L; while (c > 0x20) { ret = ret * 10 + c - '0'; c = Read(); } return n ? -ret : ret; } }