#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define int long long #define rep(i, n) for (int i = 0; i < (int)(n); i++) // [0, b) #define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); i++) // [a, b) #define rep3(i, a, b) for (int i = (int)(a); i >= (int)(b); i--) // reversed [b, a] so [a, a-1, a-2, ..., b] #define FOR(i, a) for (auto &i: a) #define ALL(obj) begin(obj), end(obj) #define MAX(x) *max_element(ALL(x)) #define MIN(x) *min_element(ALL(x)) #define SUM(x) accumulate(ALL(x), 0LL) #define LOWER_BOUND(A, key) distance(A.begin(), lower_bound(ALL(A), key)) #define UPPER_BOUND(A, key) distance(A.begin(), upper_bound(ALL(A), key)) using namespace std; const int MOD = 998244353; const int MOD2 = 1000000007; const int INF = (int)(1e13 + 7); const double EPS = 1e-14; const double PI = acos(-1); int CEIL(int a, int b) { return (a >= 0 ? (a + (b - 1)) / b : (a - (b - 1)) / b); } //ceil() for int int mod(int a, int b) { return a >= 0 ? a % b : a - (b * CEIL(a, b)); } //always return positive num int pow_mod(int a, int b) { //return x^y in order(log(y)) int res = 1; for (a %= MOD; b; a = a * a % MOD, b >>= 1) if (b & 1) res = res * a % MOD; return res; } const unsigned long long numset[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022ULL}; // 少なくとも 2^64 までは決定的 // long long型の素数判定の場合 unsigned long long mod_mul(unsigned long long a, unsigned long long b, unsigned long long mod) { long long ret = a * b - mod * (unsigned long long)((long double)(a) * (long double)(b) / (long double)(mod)); return ret + mod * (ret < 0) - mod * (ret >= (long long)mod); } unsigned long long mod_pow(unsigned long long x, unsigned long long k, unsigned long long mod) { unsigned long long res = 1; while (k) { if (k & 1) res = mod_mul(res, x, mod); x = mod_mul(x, x, mod); k >>= 1; } return res; } bool check(unsigned long long n) { if (n < 2 || ((n % 6 != 1) && (n % 6 != 5))) return (n == 2) || (n == 3); unsigned long long d = n - 1, s = 0; while (d % 2 == 0) { d /= 2; s++; } for (unsigned long long a: numset) { if (a % n == 0) return true; unsigned long long res = mod_pow(a, d, n); if (res == 1) continue; bool ok = true; for (unsigned int r = 0; r < s; r++) { if (res == n - 1) { ok = false; break; } res = mod_mul(res, res, n); } if (ok) return false; } return true; } signed main() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); int n; cin >> n; rep(i, n) { int x; cin >> x; cout << x << " " << check(x) << endl; } }