// 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 int in() { // 非負整数の入力 int n = 0, c = gc(); do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0'); return n; } void ins(char *s) { // 文字列の入力 スペース以下の文字で入力終了 do *s = gc(); while (*s++ > ' '); *(s-1) = 0; } long long s2ll(char *s) { // 非負整数への変換 long long n = 0; while (*s) n = 10*n + (*s++ & 0xf); return n; } void outs(char *s) { while (*s) pc(*s++); } // 文字列の表示 //// ラビン素数テスト #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 powmod(ull a, ull k, ull n) { ull bit = 0x2000000000000000LL, p = 1; while (bit) { if (p > 1) p = mulmod128(p, p, n); if (k & bit) p = mulmod128(p, a, n); bit >>= 1; } return p; } int ptbl[] = { 2,325,9375,28178,450775,9780504,1795265022, 0 }; int suspect(ull n) { int i, j; ull t, u, x; u = n-1, t = 0; while ((u & 1) == 0) u >>= 1, t++; for (j = 0; j < 7; j++) { x = powmod(ptbl[j], 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) { if (n <= 1) return 0; if (n <= 3) return 1; if ((n & 1) == 0) return 0; return suspect(n); } char s[25]; int main() { int n; long long x; n = in(); while (n--) { ins(s), outs(s), pc(' '); pc('0' + miller_rabin(s2ll(s))), pc('\n'); } return 0; }