// // ミラーラビン素数判定法 // /* 高速に素数判定を行う、乱択アルゴリズム 2^64までの数であれば、確実に判定可能 計算量 O((logn)^3) とにかく高速 */ #include using namespace std; #define rep(i,n) for (int i=0; i<(n); i++) #define rrep(i,n) for (int i=(n-1); i>=0; i--) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) int((x).size()) using ll = long long; using P = pair; using vi = vector; using vvi = vector; const ll INF = 8e18; 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; } template string to_string(T s); template string to_string(pair p); string to_string(char c) { return string(1, c); } string to_string(string s) { return s; } string to_string(const char s[]) { return string(s); } template string to_string(T v) { if (v.empty()) return "{}"; string ret = "{"; for (auto x : v) ret += to_string(x) + ","; ret.back() = '}'; return ret; } template string to_string(pair p) { return "{" + to_string(p.first) + ":" + to_string(p.second) + "}"; } void debug_out() { cout << endl; } template void debug_out(Head H, Tail... T) { cout << to_string(H) << " "; debug_out(T...); } #ifdef _DEBUG #define debug(...) debug_out(__VA_ARGS__) #else #define debug(...) #endif struct Miller_Rabin{ const vi v32 = {2,7,61}; const vi v64 = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; ll mod_pow(ll a, ll b, ll n){ if(b==0) return 1; if(b%2!=0) return a * mod_pow(a, b-1, n) % n; else return mod_pow(a * a % n, b / 2, n) % n; } bool check(ll n){ if(n==1) return false; if(n==2) return true; if(n%2==0) return false; auto judge = [&](vi vec)->bool{ ll d = n-1; d = d/(d&-d); for(ll a:vec){ if(n<=a) break; ll t = d; ll y = mod_pow(a,t,n); if(y==1) continue; while(y!=n-1){ y = mod_pow(y,2,n); if(y==1 || t==n-1) return false; t<<=1; } } return true; }; if(n<=4'759'123'141) return judge(v32); else return judge(v64); } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); Miller_Rabin mr; int n; cin >> n; rep(i,n){ ll a; cin >> a; cout << a << " " << (mr.check(a) ? 1:0) << endl; } }