using System; using System.Collections.Generic; using System.Linq; using static System.Console; using static System.Math; using System.Numerics; 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 uint[] l = new uint[] { 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; } var dd = (UInt128)d; var nn = (UInt128)n; for (int i = 0; i < l.Length && l[i] < n; i++) { var a = l[i]; var c = true; var x = UInt128.ModPow(a, dd, nn); if (x == 1) c = false; for (int r = 0; r < s; r++) { if (x == nn - 1) c = false; x = x * x % nn; } if (c) return false; } return true; } } public struct UInt128 { public ulong low; public ulong high; public UInt128(ulong h, ulong l) { low = l; high = h; } public static UInt128 operator +(UInt128 l, UInt128 r)//片方にもう片方足して返すのとin引数にして新しいインスタンス返すのどっちがいいんだろう { var s = new UInt128 { low = l.low + r.low, high = l.high + r.high }; if (s.low < l.low) s.high++; return s; } public static UInt128 operator -(UInt128 l, UInt128 r) { var s = new UInt128 { low = l.low - r.low, high = l.high - r.high }; if (s.low > l.low) s.high--; return s; } public static UInt128 operator *(UInt128 l, UInt128 r)//導出は n bit * n bit -> 2n bit ができないとき 上位ビット下位ビットに分割して考える { var h = l.low * r.high + l.high * r.low; var lll = l.low & 0xFFFFFFFF; var llh = l.low >> 32; var rll = r.low & 0xFFFFFFFF; var rlh = r.low >> 32; var a = lll * rll; var b = lll * rlh + llh * rll; var c = llh * rlh; if (b < lll * rlh) c += 1UL << 32; var lo = a + (b << 32); var hi = c + (b >> 32); if (lo < a) hi++; hi += h; return new UInt128 { low = lo, high = hi }; } public static UInt128 operator /(UInt128 left, UInt128 right) { if (right.high == 0) return left / right.low; if (left < right) return 0; return left.Divide(right); } public static UInt128 operator /(UInt128 left, ulong right) { if (right == (uint)right) return left / (uint)right; if (left < right) return 0; if (right.IsPowerOf2()) return left >> right.HighBitPosition(); return left.Divide(right); } public static UInt128 operator /(UInt128 left, uint right) { if (right == 0) throw new DivideByZeroException(); if (left < right) return 0; if (left.high == 0) return left.low / right; return left.Divide(right); } private ulong Divide(UInt128 denominator) { var remainder = this; ulong result = 0; var denHiBit = denominator.high.HighBitPosition(); do { var remHiBit = remainder.high.HighBitPosition(); var diff = remHiBit - denHiBit; if (diff <= 3) { // div by subtraction do { result++; remainder -= denominator; } while (remainder >= denominator); return result; } ulong resLo; if (denHiBit >= 18 && diff <= 24) { // div by divide high ulongs resLo = remainder.high / (denominator.high + 1 ); // we don't have to worry about denominator.hi being MaxValue and overflowing, because that case handled above } else { // div by shifted divide var denShift = denHiBit + 1; var den = (denominator >> denShift).low; if (den > remainder.high) { // we already know division quotient will fit in a ulong den++; if (den == 0) { // handle the rare case where the shifted den + 1 overflows denShift++; den = 1UL << 31; } resLo = DivUnchecked(remainder.high, remainder.low, den); resLo >>= denShift; } else { // ensure division quotient will fit in a ulong den++; // den + 1 can't overflow, because it's less then remainder.hi var resHi = remainder.high / den; var remHi = remainder.high - remainder.high / den * den; var tempResult = new UInt128(resHi, DivUnchecked(remHi, remainder.low, den)); tempResult >>= denShift; resLo = tempResult.low; } } result += resLo; remainder -= denominator * resLo; } while (remainder >= denominator); return result; } // denominator must be > uint.MaxValue private UInt128 Divide(ulong denominator) { ulong resHi = 0; var remHi = high; //ensure we can divide a UInt128 by a ulong, and have the quotient fit in a ulong if (remHi >= denominator) { resHi = remHi / denominator; remHi -= resHi * denominator; } return new UInt128(resHi, DivUnchecked(remHi, low, denominator)); } // denominator must be > uint.MaxValue and > the high parameter private static ulong DivUnchecked(ulong high, ulong low, ulong denominator) { unchecked { ulong hiShLo, denHi, denLo, quotHi, quotLo, mid, shLoMid, shLo, rhat, left, right; if (denominator >> 63 != 0) { mid = high; shLo = low; } else { // unwind first few iterations of loop to count leading zero bits but use // bit fiddle if more than 3 to avoid time consuming count when there are // many leading zero bits. Doing a quick test of the 4 most significant // bit positions covers about 94% of possible ulong denominator values. int s; if (denominator >> 62 != 0) s = 1; else if (denominator >> 61 != 0) s = 2; else if (denominator >> 60 != 0) s = 3; else s = ((uint)(denominator >> 32)).LeadingZeroBits(); denominator <<= s; mid = (high << s) | (low >> (64 - s)); shLo = low << s; } shLoMid = mid << 32; hiShLo = shLo >> 32; shLoMid += hiShLo; denLo = (uint)denominator; denHi = denominator >> 32; quotHi = mid / denHi; if (quotHi != 0) { rhat = mid - mid / denHi * denHi; right = (rhat << 32) | hiShLo; left = quotHi * denLo; while (quotHi != (uint)quotHi || left > right) { quotHi--; rhat += denHi; if (rhat != (uint)rhat) break; right = (rhat << 32) | hiShLo; left -= denLo; } shLoMid -= quotHi * denominator; quotHi <<= 32; } quotLo = shLoMid / denHi; rhat = shLoMid - shLoMid / denHi * denHi; right = (rhat << 32) | (uint)shLo; left = quotLo * denLo; while (quotLo != (uint)quotLo || left > right) { quotLo--; rhat += denHi; if (rhat != (uint)rhat) break; right = (rhat << 32) | (uint)shLo; left -= denLo; } return quotHi | quotLo; } } internal UInt128 Divide(uint denominator) { var hihi = (uint)(high >> 32); var reshihi = hihi == 0 ? 0 : hihi / denominator; var remainder = hihi == 0 ? (uint)high : ((ulong)(hihi - hihi / denominator * denominator) << 32) | (uint)high; var reshilo = (uint)(remainder / denominator); var remHi = remainder - reshilo * denominator; remainder = (remHi << 32) | (uint)(low >> 32); var reslohi = (uint)(remainder / denominator); remHi = remainder - reslohi * denominator; remainder = (remHi << 32) | (uint)low; var reslolo = (uint)(remainder / denominator); return new UInt128(((ulong)reshihi << 32) | reshilo, ((ulong)reslohi << 32) | reslolo); } public static UInt128 operator %(UInt128 left, UInt128 right) { if (right.high == 0) return left % right.low; if (left < right) return left; if (right.IsPowerOf2()) return left & (right - 1); return left.Mod(right); } public static ulong operator %(UInt128 left, ulong right) { if (right == (uint)right) return left % (uint)right; if (left < right) return left.low; if (right.IsPowerOf2()) return left.low & (right - 1); return left.Mod(right); } public static uint operator %(UInt128 left, uint right) { if (right == 0) throw new DivideByZeroException(); if (left < right) return (uint)left.low; if (left.high == 0) return (uint)(left.low % right); if (right.IsPowerOf2()) return (uint)left.low & (right - 1); return left.Mod(right); } // denominator must be <= this and > ulong.MaxValue internal UInt128 Mod(UInt128 denominator) { var remainder = this; var denHiBit = denominator.high.HighBitPosition(); do { var remHiBit = remainder.high.HighBitPosition(); var diff = remHiBit - denHiBit; if (diff <= 3) { // mod by subtraction do { remainder -= denominator; } while (remainder >= denominator); return remainder; } ulong resLo, den; if (denHiBit >= 18 && diff <= 24) { // mod by divide high ulongs resLo = remainder.high / (denominator.high + 1 ); // we don't have to worry about denominator.hi being MaxValue and overflowing, because that case handled above } else { // mod by shifted divide var denShift = denHiBit + 1; den = (denominator >> denShift).low; if (den > remainder.high) { // we already know division quotient will fit in a ulong den++; if (den == 0) { // handle the rare case where the shifted den + 1 overflows denShift++; den = 1UL << 31; } resLo = DivUnchecked(remainder.high, remainder.low, den); resLo >>= denShift; } else { // ensure division quotient will fit in a ulong den++; // den + 1 can't overflow, because it's less then remainder.hi var resHi = remainder.high / den; var remHi = remainder.high - remainder.high / den * den; var tempResult = new UInt128(resHi, DivUnchecked(remHi, remainder.low, den)); tempResult >>= denShift; resLo = tempResult.low; } } remainder -= denominator * resLo; } while (remainder >= denominator); return remainder; } // denominator must be > uint.MaxValue internal ulong Mod(ulong denominator) { unchecked { var high = this.high; var low = this.low; //ensure we can divide a UInt128 by a ulong, and have the quotient fit in a ulong if (high >= denominator) high -= high / denominator * denominator; if (high == 0) return low - low / denominator * denominator; ulong hiShLo, denHi, denLo, quotHi, quotLo, mid, shLoMid, shLo, rhat, left, right; int shift; if (denominator >> 63 != 0) { mid = high; shLo = low; shift = 0; } else { // unwind first few iterations of loop to count leading zero bits but use // bit fiddle if more than 3 to avoid time consuming count when there are // many leading zero bits. Doing a quick test of the 4 most significant // bit positions covers about 94% of possible ulong denominator values. if (denominator >> 62 != 0) shift = 1; else if (denominator >> 61 != 0) shift = 2; else if (denominator >> 60 != 0) shift = 3; else shift = ((uint)(denominator >> 32)).LeadingZeroBits(); denominator <<= shift; mid = (high << shift) | (low >> (64 - shift)); shLo = low << shift; } shLoMid = mid << 32; hiShLo = shLo >> 32; shLoMid += hiShLo; denLo = (uint)denominator; denHi = denominator >> 32; quotHi = mid / denHi; if (quotHi != 0) { rhat = mid - mid / denHi * denHi; right = (rhat << 32) | hiShLo; left = quotHi * denLo; while (quotHi != (uint)quotHi || left > right) { quotHi--; rhat += denHi; if (rhat != (uint)rhat) break; right = (rhat << 32) | hiShLo; left -= denLo; } shLoMid -= quotHi * denominator; } quotLo = shLoMid / denHi; rhat = shLoMid - shLoMid / denHi * denHi; right = (rhat << 32) | (uint)shLo; left = quotLo * denLo; while (quotLo != (uint)quotLo || left > right) { quotLo--; rhat += denHi; if (rhat != (uint)rhat) break; right = (rhat << 32) | (uint)shLo; left -= denLo; } return ((shLoMid << 32) + ((uint)shLo - quotLo * denominator)) >> shift; } } internal uint Mod(uint denominator) { var hihi = (uint)(high >> 32); var remainder = hihi == 0 ? (uint)high : ((ulong)(hihi - hihi / denominator * denominator) << 32) | (uint)high; var remHi = (remainder % denominator) << 32; remainder = remHi | (uint)(low >> 32); remHi = (remainder % denominator) << 32; remainder = remHi | (uint)low; return (uint)(remainder % denominator); } public static UInt128 operator &(UInt128 l, UInt128 r) { return new UInt128 { low = l.low & r.low, high = l.high & r.high }; } public static UInt128 operator |(UInt128 l, UInt128 r) { return new UInt128 { low = l.low | r.low, high = l.high | r.high }; } public static UInt128 operator ^(UInt128 l, UInt128 r) { return new UInt128 { low = l.low ^ r.low, high = l.high ^ r.high }; } public static UInt128 operator <<(UInt128 l, int r) { r &= 0x7F; if (r >= 64) { l.high = l.low << r - 64; l.low = 0; } else { l.high <<= r; l.high |= l.low >> 64 - r; l.low <<= r; } return l; } public static UInt128 operator >>(UInt128 l, int r) { r &= 0x7F; if (r >= 64) { l.low = l.high >> r - 64; l.high = 0; } else { l.low >>= r; l.low |= l.high << 64 - r; l.high >>= r; } return l; } public static bool operator ==(UInt128 l, UInt128 r) { return l.low == r.low && l.high == r.high; } public static bool operator !=(UInt128 l, UInt128 r) { return l.low != r.low || l.high != r.high; } public static bool operator >(UInt128 l, UInt128 r) { return l.high > r.high || l.low > r.low; } public static bool operator <(UInt128 l, UInt128 r) { return l.high < r.high || l.low < r.low; } public static bool operator >=(UInt128 l, UInt128 r) { if (l.high > r.high) return true; if (l.high == r.high && l.low >= r.low) return true; return false; } public static bool operator <=(UInt128 l, UInt128 r) { if (l.high < r.high) return true; if (l.high == r.high && l.low <= r.low) return true; return false; } public static UInt128 operator ~(UInt128 v) { v.low = ~v.low; v.high = ~v.high; return v; } public static UInt128 operator +(UInt128 v) { return v; } public static UInt128 operator ++(UInt128 v) { return v + 1; } public static UInt128 operator --(UInt128 v) { return v - 1; } public static explicit operator UInt128(sbyte v) { return new UInt128 { low = (ulong)v }; } public static implicit operator UInt128(byte v) { return new UInt128 { low = v }; } public static explicit operator UInt128(short v) { return new UInt128 { low = (ulong)v }; } public static implicit operator UInt128(ushort v) { return new UInt128 { low = v }; } public static explicit operator UInt128(int v) { return new UInt128 { low = (ulong)v }; } public static implicit operator UInt128(uint v) { return new UInt128 { low = v }; } public static explicit operator UInt128(long v) { return new UInt128 { low = (ulong)v }; } public static implicit operator UInt128(ulong v) { return new UInt128 { low = v }; } public static explicit operator UInt128(BigInteger v) { var ret = new UInt128 { low = (ulong)v }; v >>= 64; ret.high = (ulong)v; return ret; } public static explicit operator sbyte(UInt128 v) { return (sbyte)(v.low & 0x7F); } public static explicit operator byte(UInt128 v) { return (byte)v.low; } public static explicit operator short(UInt128 v) { return (short)(v.low & 0x7FFF); } public static explicit operator ushort(UInt128 v) { return (ushort)v.low; } public static explicit operator int(UInt128 v) { return (int)v.low & int.MaxValue; } public static explicit operator uint(UInt128 v) { return (uint)v.low; } public static explicit operator long(UInt128 v) { return (long)v.low & long.MaxValue; } public static explicit operator ulong(UInt128 v) { return v.low; } public static implicit operator BigInteger(UInt128 v) { return (new BigInteger(v.high) << 64) | v.low; } public static UInt128 ModPow(UInt128 x, UInt128 n, UInt128 m) { var res = (UInt128)1; while (n != 0) { if ((n & 1) == 1) res = res * x % m; x = x * x % m; n >>= 1; } return res; } public static UInt128 Parse(string s)// -0を許容して -nはovfとして扱いたい 要はuint,ulongと挙動をそろえたい { if (s is null) throw new ArgumentNullException(); s = s.Trim(); if (s.Length == 0) throw new FormatException(); if (s[0] == '+') { if (s.Length == 1) throw new FormatException(); else s = s.Substring(1); } var a = 0; for (int i = 0; i < s.Length; i++) { if (s[i] != '0') { a = i; break; } } s = s.Substring(a == s.Length - 1 ? a - 1 : a); if (s.Length > 39) throw new FormatException(); for (int i = 0; i < s.Length; i++) { if ((uint)(s[i] - '0') > '9') throw new FormatException(); } if (s.Length == 39 && s.CompareTo("340282366920938463463374607431768211456") != 1) throw new OverflowException(); var ret = new UInt128(); for (int i = 0; i < s.Length; i++) { ret *= 10; ret += (uint)(s[i] - '0'); } return ret; } public override string ToString() { if (this == 0) return "0"; var a = this; var ret = new List(40); while (a != 0) { ret.Add((char)((int)(a % 10) + '0')); a /= 10; } ret.Reverse(); return new string(ret.ToArray()); } public override bool Equals(object obj) { return base.Equals(obj); } public override int GetHashCode() { return base.GetHashCode(); } } internal static class SoftWxNumerics { private static readonly byte[] DeBruijnLsBsSet = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; public static int HighBitPosition(this uint value) { if (value == 0) return -1; value |= value >> 1; value |= value >> 2; value |= value >> 4; value |= value >> 8; return DeBruijnLsBsSet[unchecked((value | value >> 16) * 0x07c4acddu) >> 27]; } public static int HighBitPosition(this ulong value) { uint high = (uint)(value >> 32); return high != 0 ? 32 + HighBitPosition(high) : HighBitPosition((uint)value); } public static int LeadingZeroBits(this uint value) { return unchecked(31 - HighBitPosition(value)); } public static bool IsPowerOf2(this uint value) { return (value & unchecked(value - 1)) == 0 && value != 0; } public static bool IsPowerOf2(this ulong value) { return (value & unchecked(value - 1UL)) == 0 && value != 0; } public static bool IsPowerOf2(this UInt128 value) { return (value & value - 1) == 0 && value != 0; } }