// yukicoder 3030 ミラー・ラビン素数判定法のテスト // 2019.5.18 bal4u #include #include typedef long long ll; typedef unsigned long long ull; //// 高速入出力 #if 1 #define gc() getchar_unlocked() #define pc(c) putchar_unlocked(c) #else #define gc() getchar() #define pc(c) putchar(c) #endif ll in(int echo) { // 非負整数の入力 ll n = 0; int c; while (1) { if ((c = gc()) < '0') break; if (echo) pc(c); n = 10 * n + (c & 0xf); } return n; } //// ラビン素数テスト #if 1 #define mulmod128(a,b,n) ((__int128_t)a*b % n) #else #define mod(a,m) ((a)%(m)) ull mulmod128(ull a, ull b, ull m) { ull ans = 0; a = mod(a, m), b = mod(b, m); while (b > 0) { if (b & 1) ans = mod(ans + a, m); a = mod(a << 1, m); b >>= 1; } return ans; } #endif ull modpow(ull x, ull p, ull n) { ull r = 1; while (p) { if (p & 1) r = mulmod128(r, x, n); x = mulmod128(x, x, n); p >>= 1; } return r; } unsigned xorshift() { static unsigned y = 2463534242; y = y ^ (y << 13), y = y ^ (y >> 17), y = y ^ (y << 5); return y; } //int ptbl[] = { 2,325,9375,28178,450775,9780504,1795265022, 0 }; int suspect(ull n) { int i, j, b; ull t, u, x; u = n-1, t = 0; while ((u & 1) == 0) u >>= 1, t++; for (j = 0; j < 6; j++) { if ((b = xorshift() % n) == 0) continue; // if ((b = ptbl[j] % n) == 0) continue; x = modpow(b, u, n); if (x == 1 || x == n-1) continue; for (i = 1; i < t; i++) { x = mulmod128(x, x, n); if (x == 1) return 0; if (x == n-1) break; } if (i == t) return 0; } return 1; } int miller_rabin(ull n) { int p[10] = { 0,0,1,1,0,1,0,1,0,0 }; if (n < 10) return p[n]; if ((n & 1) == 0) return 0; if (n % 5 == 0) return 0; return suspect(n); } int main() { int n; n = in(0); while (n--) { ll x = in(1); pc(' '), pc('0' + miller_rabin(x)), pc('\n'); } return 0; }