#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)) 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; } static u64 _state_ = 88172645463325252ULL; const f64 _R_ = 1.0 / 0xffffffffffffffff; u64 next_rand(void) { _state_ = _state_ ^ (_state_ << 7); return _state_ = _state_ ^ (_state_ >> 9); } void rand_init(u64 seed) { _state_ += seed; (void)next_rand(); } u64 random_range(u64 l, u64 r) {/* [l, r] */ return next_rand() % (r - l + 1) + l; } f64 probability(void) { return next_rand() * _R_; } u64 _inv(u64 mod) { FastInt i; u64 u = 1, v = 0, x = 1ULL << 63; for (i = 0; i < 64; i++) { if (u & 1) u = (u + mod) >> 1, v = (v >> 1) + x; else u >>= 1, v >>= 1; } return -v; } u64 _r2(u64 mod) { return (u128)(i128)-1 % mod + 1; } u64 _one(u64 mod) { return -1ULL % mod + 1; } u64 _MR(u128 x, u64 inv, u64 mod) { i64 z = (x >> 64) - ((((u64)x * inv) * (u128)mod) >> 64); return z < 0 ? z + mod : (u64)z; } u64 to_montgomery_form(u64 a, u64 r2, u64 inv, u64 mod) { return _MR((u128)a * r2, inv, mod); } u64 from_montgomery_form(u64 a, u64 inv, u64 mod) { return _MR((u128)a, inv, mod); } u64 mulmod_MR(u64 x, u64 y, u64 r2, u64 inv, u64 mod) { return _MR((u128)r2 * _MR((u128)x * y, inv, mod), inv, mod); } u64 powmod_MR(u64 a, u64 n, u64 r2, u64 inv, u64 mod) { u64 res = _one(mod); u64 A = to_montgomery_form(a, r2, inv, mod); while (n > 0) { if (n & 1) res = _MR((u128)res * A, inv, mod); A = _MR((u128)A * A, inv, mod); n >>= 1; } return from_montgomery_form(res, inv, mod); } bool is_prime(u64 n) { if (n <= 3) return n == 2 || n == 3; if (!(n & 1)) return false; u64 r2 = _r2(n); u64 inv = _inv(n); u64 s = CTZ(n - 1); u64 d = (n - 1) >> s; if (n < (1ull << 30)) { u64 as[] = {2,7,61}; for (FastInt i = 0; i < 3; i++) { if (_MR(as[i], inv, n) == 0) return true; u64 res = powmod_MR(as[i], d, r2, inv, n); if (res == 1) continue; bool ok = true; for (u64 r = 0; r < s; r++) { if (res == n - 1) { ok = false; break; } res = mulmod_MR(res, res, r2, inv, n); } if (ok) return false; } return true; } else { u64 as[] = {2,325,9375,28178,450775,9780504,1795265022}; for (FastInt i = 0; i < 7; i++) { if (_MR(as[i], inv, n) == 0) return true; u64 res = powmod_MR(as[i], d, r2, inv, n); if (res == 1) continue; bool ok = true; for (u64 r = 0; r < s; r++) { if (res == n - 1) { ok = false; break; } res = mulmod_MR(res, res, r2, inv, n); } if (ok) return false; } return true; } } u64 invmod_MR(u64 a, u64 r2, u64 inv, u64 mod) { // assert(is_prime(mod)); if (_gcd_(a, mod) != 1) return -1; return powmod_MR(a, mod - 2, r2, inv, mod); } u64 divmod_MR(u64 x, u64 y, u64 r2, u64 inv, u64 mod) { // assert(is_prime(mod)); u64 z = powmod_MR(y, mod - 2, r2, inv, mod); return mulmod_MR(x, z, r2, inv, mod); } bool Miller_Rabin(u64 n) { // step 1. if (_gcd_(n, 15) != 1) return false; u64 r2 = _r2(n); u64 inv = _inv(n); // step 2. u64 fermat_test = powmod_MR(2, (n - 1) >> 1, r2, inv, n); if (fermat_test != 1 && fermat_test != n - 1) return false; u64 s = CTZ(n - 1); u64 d = (n - 1) >> s; // step 3. for (FastInt _ = 0; _ < 6; _++) { u64 a = random_range(1, n - 1); bool ok = true; for (u64 r = 0; r < s; r++) ok &= ((n - 1) != powmod_MR(a, (1 << r) * d , r2, inv, n)); if (powmod_MR(a, d, r2, inv, n) != 1 && ok) return false; } return true; } void Main(void) { FastInt Q = read_int(); while (Q--) { u64 x = inu(); outu(x); SP(); outu(Miller_Rabin(x)); NL(); } } int main(void) { Main(); return 0; }