#include #include #include #include #include typedef int8_t i8; typedef int16_t i16; typedef int32_t i32; typedef int64_t i64; typedef __int128_t i128; typedef uint8_t u8; typedef uint16_t u16; typedef uint32_t u32; typedef uint64_t u64; typedef __uint128_t u128; typedef struct Montgomery64 { u64 m, r, n2; u64 x; } m64; u64 MR(m64 m_, u128 b) { return (b + (u128)((u64)b * m_.r) * m_.m) >> 64; } u64 RM(m64 m_) { u64 y = MR(m_, m_.x); return y >= m_.m ? y - m_.m : y; } m64 make_montgomery(u64 n, u64 mod) { m64 result; assert(mod != 0); assert((mod & 1) != 0); result.m = mod; result.n2 = -(u128)(mod) % mod; result.r = mod; for (int _ = 0; _ < 5; _++) result.r *= 2 - result.m * result.r; result.r = -result.r; result.x = MR(result, (u128)n * result.n2); return result; } m64 plusmod(m64 p, m64 q) { p.x += q.x - (q.m << 1); p.x = ((i64)p.x < 0 ? p.x + (p.m << 1) : p.x); return p; } m64 minusmod(m64 p, m64 q) { p.x -= q.x; p.x = ((i64)p.x < 0 ? p.x + (p.m << 1) : p.x); return p; } m64 mulmod(m64 p, m64 q) { p.x = MR(p, (u128)p.x * q.x); return p; } m64 powmod(m64 p, u64 n) { m64 y = make_montgomery(1, p.m); m64 z = p; for (; n; n >>= 1, z = mulmod(z, z)) if (n & 1) y = mulmod(y, z); return y; } bool eq(m64 p, m64 q) { return (p.x >= p.m ? p.x - p.m : p.x) == (q.x >= q.m ? q.x - q.m : q.x); } bool not_eq(m64 p, m64 q) { return !eq(p, q); } bool is_prime(const u64 n) { if (n == 2 || n == 3 || n == 5 || n == 7) return true; if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) return false; if (n < 121) return n > 1; const u64 m = n - 1; const u64 d = m >> __builtin_ctzll(m); const m64 one = make_montgomery(1, n), minus_one = make_montgomery(m, n); const u64 check1[3] = {2, 7, 61}; const u64 check2[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; if (n < (1ull << 32)) { for (int i = 0; i < 3; i++) { m64 a = make_montgomery(check1[i], n); m64 y = powmod(a, d); u64 t = d; while (not_eq(y, one) && not_eq(y, minus_one) && t != m) y = mulmod(y, y), t <<= 1; if (not_eq(y, minus_one) && t % 2 == 0) return false; } } else { for (int i = 0; i < 7; i++) { m64 a = make_montgomery(check2[i], n); m64 y = powmod(a, d); u64 t = d; while (not_eq(y, one) && not_eq(y, minus_one) && t != m) y = mulmod(y, y), t <<= 1; if (not_eq(y, minus_one) && t % 2 == 0) return false; } } return true; } int main() { int i, n; scanf("%d", &n); u64 u; for (i = 0; i < n; i++) { scanf("%lu", &u); printf("%lu ", u); if (is_prime(u)) printf("1\n"); else printf("0\n"); } return 0; }