#include "bits/stdc++.h" using namespace std; #define int long long random_device rd; mt19937 mt(rd()); int modpro(int x, int n, int md) { if (!n)return 0; int res = modpro((x + x)%md, n >> 1, md); if (n & 1)res = (res + x) % md; return res; } int modpow(int x, int n, int md) { if (!n)return 1; int res = modpow(modpro(x,x,md), n >>1, md); if (n & 1)res = modpro(res,x,md); return res; } int gcd(int a, int b) { if (!b)return a; return gcd(b, a%b); } bool isprime(int p) { if (p == 2 || p == 3 || p == 5)return true; if (p == 1 || p == 4)return false; for(int z=0;z<5000;++z) { int b = mt() % (p - 2) + 2; if (gcd(b, p) > 1) { return false; } if (modpow(b, p - 1, p) > 1) { return false; } } return true; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; int p; for (int i = 0; i < n; i++) { cin >> p; cout << p; if (isprime(p))puts(" 1"); else puts(" 0"); } }