#pragma GCC target("avx2") #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include /* signed integer */ typedef int8_t i8; typedef int16_t i16; typedef int32_t i32; typedef int64_t i64; typedef __int128_t i128; /* unsigned integer */ typedef uint8_t u8; typedef uint16_t u16; typedef uint32_t u32; typedef uint64_t u64; typedef __uint128_t u128; /* floating point number */ typedef float f32; typedef double f64; typedef long double f80; typedef int FastInt; /* io */ static inline FastInt read_int(void) { FastInt c, x = 0, f = 1; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; } static inline i64 in(void) { i64 c, x = 0, f = 1; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; } static inline u64 inu(void) { u64 c, x = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; } static inline void write_int(FastInt x) { if (x < 0) { putchar_unlocked('-'); x = -x; } if (x >= 10) write_int(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } static inline void out(i64 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } if (x >= 10) out(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } static inline void outu(u64 x) { if (x >= 10) outu(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } static inline void NL(void) { putchar_unlocked('\n'); } static inline void SP(void) { putchar_unlocked(' '); } /* MACROS */ #define POPCNT(a) __builtin_popcountll((a)) #define CTZ(a) __builtin_ctzll((a)) #define CLZ(a) __builtin_clzll((a)) #define LSBit(a) ((a)&(-(a))) #define CLSBit(a) ((a)&((a)-(1))) #define HAS_SINGLE_BIT(a) (POPCNT((a))==1) #define BIT_CEIL(a) ((!(a))?(1):((POPCNT(a))==(1)?((1ull)<<((63)-CLZ((a)))):((1ull)<<((64)-CLZ(a))))) #define BIT_FLOOR(a) ((!(a))?(0):((1ull)<<((63)-CLZ((a))))) #define BIT_WIDTH(a) ((a)?((64)-CLZ((a))):(0)) #define _ROTL(x, s) (((x)<<((s)%(64)))|(((x)>>((64)-((s)%(64)))))) #define _ROTR(x, s) (((x)>>((s)%(64)))|(((x)<<((64)-((s)%(64)))))) #define ROTL(x, s) (((s)==(0))?(0):(((s)<(0))?(_ROTR((x),-(s))):(_ROTL((x),(s))))) #define ROTR(x, s) (((s)==(0))?(0):(((s)<(0))?(_ROTL((x),-(s))):(_ROTR((x),(s))))) #define SWAP(a, b) (((a)^=(b)),((b)^=(a)),((a)^=(b))) #define MAX(a, b) ((a)>(b)?(a):(b)) #define MIN(a, b) ((a)<(b)?(a):(b)) /* binary gcd/lcm */ u64 _gcd_(u64 a, u64 b) { if (!a || !b) return a | b; FastInt shift = CTZ(a | b); a >>= CTZ(a); do { b >>= CTZ(b); if (a > b) SWAP(a, b); b -= a; } while (b); return a << shift; } u64 _lcm_(u64 a, u64 b) { return a / _gcd_(a, b) * b; } /* montgomery modular multiplication 64-bit */ typedef u64 Montgomery64; Montgomery64 _one_64(u64 mod) { return -1ull % mod + 1; } Montgomery64 _r2_64(u64 mod) { return (u128)(i128)-1 % mod + 1; } Montgomery64 _inv_64(u64 mod) { u64 u = 1, v = 0, x = 1ULL << 63; for (FastInt i = 0; i < 64; i++) { if (u & 1) u = (u + mod) >> 1, v = (v >> 1) + x; else u >>= 1, v >>= 1; } return -v; } Montgomery64 _MR_64(u128 a, Montgomery64 inv, u64 mod) { i64 A = (a >> 64) - ((((u64)a * inv) * (u128)mod) >> 64); return A < 0 ? A + mod : (u64)A; } Montgomery64 _to_montgomery_64(u64 a, Montgomery64 r2, Montgomery64 inv, u64 mod) { return _MR_64((u128)a * r2, inv, mod); } u64 _from_montgomery_64(Montgomery64 A, Montgomery64 inv, u64 mod) { u64 temp = _MR_64((u128)A, inv, mod) - mod; return temp + (mod & -(temp >> 63u)); } Montgomery64 add_MR_64(Montgomery64 A, Montgomery64 B, Montgomery64 r2, Montgomery64 inv, u64 mod) { A += B - (mod << 1u); A += (mod << 1u) & -(A >> 63u); return A; } Montgomery64 sub_MR_64(Montgomery64 A, Montgomery64 B, Montgomery64 r2, Montgomery64 inv, u64 mod) { A -= B; A += (mod << 1u) & -(A >> 63u); return A; } Montgomery64 min_MR_64(Montgomery64 A, Montgomery64 r2, Montgomery64 inv, u64 mod) { return sub_MR_64(0, A, r2, inv, mod); } Montgomery64 mul_MR_64(Montgomery64 A, Montgomery64 B, Montgomery64 inv, u64 mod) { return _MR_64((u128)A * B, inv, mod); } Montgomery64 pow_MR_64(Montgomery64 A, i64 n, Montgomery64 inv, u64 mod) { Montgomery64 ret = _one_64(mod), mul = A; while (n > 0) { if (n & 1) ret = mul_MR_64(ret, mul, inv, mod); mul = mul_MR_64(mul, mul, inv, mod); n >>= 1; } return ret; } Montgomery64 inv_MR_64(Montgomery64 A, Montgomery64 inv, u64 mod) { return pow_MR_64(A, (i64)mod - 2, inv, mod); } Montgomery64 div_MR_64(Montgomery64 A, Montgomery64 B, Montgomery64 inv, u64 mod) { return mul_MR_64(A, inv_MR_64(B, inv, mod), inv, mod); } bool eq_MR_64(Montgomery64 A, Montgomery64 B, Montgomery64 inv, u64 mod) { return _from_montgomery_64(A, inv, mod) == _from_montgomery_64(B, inv, mod); } bool neq_MR_64(Montgomery64 A, Montgomery64 B, Montgomery64 inv, u64 mod) { return _from_montgomery_64(A, inv, mod) != _from_montgomery_64(B, inv, mod); } bool is_prime_64(u64 n) { if (n <= 10ull) return n == 2ull || n == 3ull || n == 5ull || n == 7ull; if (!(n & 1)) return false; if (_gcd_(n, 15) != 1) return false; Montgomery64 r2 = _r2_64(n), inv = _inv_64(n); Montgomery64 e = _one_64(n), rev = _to_montgomery_64(n - 1, r2, inv, n); Montgomery64 two = _to_montgomery_64(2ull, r2, inv, n); Montgomery64 fermat = pow_MR_64(two, (n - 1) >> 1, inv, n); if (fermat != e && fermat != rev) return false; u64 s = CTZ(n - 1); u64 d = (n - 1) >> s; u64 as[] = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 }; for (FastInt i = 0; i < 7; i++) { if (_MR_64((u128)as[i], inv, n) == 0) return true; Montgomery64 A = _to_montgomery_64(as[i], r2, inv, n); Montgomery64 res = pow_MR_64(A, d, inv, n); if (res == e) continue; bool ok = true; for (u64 r = 0; r < s; r++) { if (res == rev) { ok = false; break; } res = mul_MR_64(res, res, inv, n); } if (ok) return false; } return true; } void Main(void) { FastInt Q = read_int(); while (Q--) { u64 x = inu(); outu(x); SP(); outu(is_prime_64(x)); NL(); } } int main(void) { Main(); return 0; }