#include using namespace std; //g++ temp.cpp -DLOCAL でコンパイルする #define LOCAL struct Miller_Rabin { unsigned long long mul_mod(unsigned long long a, unsigned long long b, unsigned long long m) { unsigned long long ans = 0; #ifdef LOCAL if(a > b) std::swap(a, b); if(m >> 63 & 1){ assert(false); unsigned long long overv = ((unsigned long long)(1) << 63) - m + ((unsigned long long)(1) << 63); while(b){ if(b & 1){ if(__builtin_add_overflow(ans, a, &ans)){ ans += overv; } if(ans >= m) ans -= m; } if(__builtin_add_overflow(a, a, &a)) a += overv; if(a >= m) a -= m; b >>= 1; } }else{ while(b){ if(b & 1){ ans += a; if(ans >= m) ans -= m; } if((a <<= 1) >= m) a -= m; b >>= 1; } } #else ans = (unsigned long long)((__int128)(a) * (__int128)(b) % m); #endif return ans; } unsigned long long pow_mod(unsigned long long x, unsigned long long n, unsigned long long m) { if (m == 1) return 0; unsigned long long r = 1; unsigned long long y = x % m; while (n) { if (n & 1) r = mul_mod(r, y, m); y = mul_mod(y, y, m); n >>= 1; } return r; } bool is_prime(unsigned long long n) { if (n <= 1) return false; if (n == 2) return true; if (n % 2 == 0) return false; unsigned long long d = n - 1; while (d % 2 == 0) d /= 2; constexpr long long bases[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 31, 61}; for (long long a : bases) { if(n == a) return true; unsigned long long t = d; unsigned long long y = pow_mod(a, t, n); while (t != n - 1 && y != 1 && y != n - 1) { y = mul_mod(y, y, n); t <<= 1; } if (y != n - 1 && t % 2 == 0) return false; } return true; } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); Miller_Rabin MR; int T; cin >> T; while(T--){ unsigned long long v; cin >> v; cout << v << ' ' << MR.is_prime(v) << '\n'; } }