#include #include #include #include #include #include #include using namespace std; mt19937 mt(123456); bool miller_rabin(long long n) { if (n <= 1) return false; if (n == 2) return true; long long s = n - 1; int e = 0; for (; s % 2 == 0; s /= 2) e++; // n-1 = s 2^e auto mul = [&](long long a, long long b, long long m) { long long r = 0; for (; b > 0; b >>= 1) { if (b & 1) { r += a; if (r >= m) r -= m; } a += a; if (a >= m) a -= m; } return r; }; for (int ii = 0; ii < 5; ii++) { long long x = std::uniform_int_distribution(2, n - 1)(mt); // x^s long long r = 1; for (long long i = s; i > 0; i >>= 1) { if (i & 1) r = mul(r, x, n); x = mul(x, x, n); } if (r == 1 || r == n - 1) continue; for (int i = 0; i < e; i++) { r = mul(r, r, n); if (r == n - 1) break; } if (r != n - 1) return false; } return true; } bool is_prime(long long n) { for (long long i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return n != 1; } int main() { int n; cin >> n; while (n--) { long long x; scanf("%lld", &x); printf("%lld %d\n", x, miller_rabin(x)); } }