#include using namespace std; #define rep(i,m,n) for(int i=m;i>= 1; } return ans; } unsigned long long ll_power(unsigned long long a, unsigned long long b, unsigned long long r) { unsigned long long ans = 1; while (b != 0) { if ((b & 1) == 1) { ans = ll_product(ans, a, r); } a = ll_product(a, a, r); b >>= 1; } return ans; } bool primality_test(unsigned long long num) { if (num == 2) { return true; } if ((num & 1) == 0 || num == 1) { return false; } unsigned long long d = (num - 1) >> 1; int s = 1; while ((d & 1) == 0) { d >>= 1; s++; } for (int k = 0; k < 9; k++) { bool is_prime = false; unsigned long long a = sprp_base[k]; if (num > a) { unsigned long long r = ll_power(a, d, num); if (r == 1 || r == num - 1) { is_prime = true; } for (int i = 0; i < s; i++) { r = ll_product(r, r, num); if (r == num - 1) { is_prime = true; } } if (!is_prime) { return false; } } } return true; } int main() { int n; std::cin >> n; for (int i = 0; i < n; i++) { unsigned long long hoge; std::cin >> hoge; std::cout << hoge << " " << std::flush; if (primality_test(hoge)) { std::cout << "1" << std::endl; } else { std::cout << "0" << std::endl; } } return 0; }