/** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author aajisaka */ #include using namespace std; void debug_out() { cerr << endl; } template void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif #define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr) #define rep(i,n) for(int i=0; i<(int)(n); i++) #define all(v) v.begin(), v.end() template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } using ll = long long; using P = pair; constexpr long double PI = 3.14159265358979323846264338327950288L; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // TODO: Create and use 64bit mint class to avoid % function. This speed up to ~10x. struct Miller { const vector v = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; unsigned long long modpow(unsigned long long x, unsigned long long k, unsigned long long m){ unsigned long long res = 1; while(k > 0){ if(k&1){ res = __uint128_t(res) * x % m; } k /= 2; x = __uint128_t(x) * x % m; } return res; } bool suspect(unsigned long long a, unsigned long long s, unsigned long long d, unsigned long long n) { unsigned long long x = modpow(a, d, n); if (x == 1) return true; for(int r = 0; r < s; r++) { if (x == n-1) return true; x = __uint128_t(x) * x % n; } return false; } // check if n is prime bool check(unsigned long long n ) { if (n < 2 || (n > 2 && n % 2 == 0)) return false; unsigned long long d = n - 1; unsigned long long s = 0; while (!(d & 1)) { d >>= 1; s++; } for (auto a: v) { if (a >= n) break; if (!suspect(a, s, d, n)) return false; } return true; } }; class TestMillerRabin { public: void solve(istream& cin, ostream& cout) { SPEED; int n; cin >> n; Miller miller; while(n--) { ll p; cin >> p; cout << p << ' '; cout << (miller.check(p) ? 1 : 0) << '\n'; } } }; signed main() { TestMillerRabin solver; std::istream& in(std::cin); std::ostream& out(std::cout); solver.solve(in, out); return 0; }