#include #include #include #include struct Dyn_Mont_mint64 { using i64 = std::int64_t; using u64 = std::uint64_t; using u128 = __uint128_t; // r * m === -1 (mod 1 << 64) // n2 === 1 <<< 128 (mod m) inline static u64 m, r, n2; static void set_mod(u64 m) { assert(m < (1ull << 62)); assert((m & 1) == 1); Dyn_Mont_mint64::m = m; n2 = -u128(m) % m; r = m; for (int _ = 0; _ < 5; ++_) r *= 2 - m * r; r = -r; assert(r * m == -1ull); } static u64 reduce(u128 b) { return (b + u128(u64(b) * r) * m) >> 64; } u64 x; Dyn_Mont_mint64() : x(0) { } Dyn_Mont_mint64(u64 x) : x(reduce(u128(x) * n2)) { } u64 val() const { u64 y = reduce(x); return y >= m ? y - m : y; } Dyn_Mont_mint64 &operator+=(Dyn_Mont_mint64 y) { x += y.x - (m << 1); x = (i64(x) < 0 ? x + (m << 1) : x); return *this; } Dyn_Mont_mint64 &operator-=(Dyn_Mont_mint64 y) { x -= y.x; x = (i64(x) < 0 ? x + (m << 1) : x); return *this; } Dyn_Mont_mint64 &operator*=(Dyn_Mont_mint64 y) { x = reduce(u128(x) * y.x); return *this; } Dyn_Mont_mint64 operator+(Dyn_Mont_mint64 y) const { return Dyn_Mont_mint64(*this) += y; } Dyn_Mont_mint64 operator-(Dyn_Mont_mint64 y) const { return Dyn_Mont_mint64(*this) -= y; } Dyn_Mont_mint64 operator*(Dyn_Mont_mint64 y) const { return Dyn_Mont_mint64(*this) *= y; } bool operator==(Dyn_Mont_mint64 y) const { return (x >= m ? x - m : x) == (y.x >= m ? y.x - m : y.x); } bool operator!=(Dyn_Mont_mint64 y) const { return not operator==(y); } Dyn_Mont_mint64 pow(u64 n) const { Dyn_Mont_mint64 y = 1, z = *this; for ( ; n; n >>= 1, z *= z) if (n & 1) y *= z; return y; } }; using m64 = Dyn_Mont_mint64; bool is_prime(const std::uint64_t x) { if (x == 2 or x == 3 or x == 5 or x == 7) return true; if (x % 2 == 0 or x % 3 == 0 or x % 5 == 0 or x % 7 == 0) return false; if (x < 121) return x > 1; const std::uint64_t d = (x - 1) >> __builtin_ctzll(x - 1); m64::set_mod(x); const m64 one{1}, rev{x - 1}; auto ok = [&](std::uint64_t a) { auto y = m64(a).pow(d); std::uint64_t t = d; while (y != one and y != rev and t != x-1) y *= y, t <<= 1; if (y != rev and t % 2 == 0) return false; return true; }; if (x < (1ull << 32)) { for (std::uint64_t a : { 2, 7, 61 }) if (not ok(a)) return false; } else { for (std::uint64_t a : { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 }) { if (x <= a) return true; if (not ok(a)) return false; } } return true; } int main() { std::uint64_t n; scanf("%lu", &n); while (n--) { std::uint64_t x; scanf("%lu", &n); printf("%lu %d\n", x, is_prime(x)); } }