#pragma GCC optimize("O3") #pragma GCC target("avx2") #pragma GCC optimize("fast-math") #define _GNU_SOURCE #include #include #include #include #include #include #include #include #include #include typedef int8_t i8; typedef int16_t i16; typedef int32_t i32; typedef int64_t i64; typedef __int128_t i128; typedef uint8_t u8; typedef uint16_t u16; typedef uint32_t u32; typedef uint64_t u64; typedef __uint128_t u128; typedef float f32; typedef double f64; typedef long double f80; #define MIN(a, b) ((a) < (b) ? (a) : (b)) #define MAX(a, b) ((a) > (b) ? (a) : (b)) #define SWAP_REF(a, b) \ do { \ (a) ^= (b); \ (b) ^= (a); \ (a) ^= (b); \ } \ while(0); #define CTZ32(a) ((a) ? __builtin_ctz((a)) : (32)) #define CTZ64(a) ((a) ? __builtin_ctzll((a)) : (64)) #define CLZ32(a) ((a) ? __builtin_clz((a)) : (32)) #define CLZ64(a) ((a) ? __builtin_clzll((a)) : (64)) #define POPCNT32(a) ((a) ? __builtin_popcount((a)) : (0)) #define POPCNT64(a) ((a) ? __builtin_popcountll((a)) : (0)) #define MSB32(a) ((a) ? ((31) - __builtin_clz((a))) : (-1)) #define MSB64(a) ((a) ? ((63) - __builtin_clzll((a))) : (-1)) #define LSBit(a) ((a) & (-(a))) #define CLSBit(a) ((a) & ((a) - (1))) #define _ROTL32_INNER(x, l) (((x) << (l)) | ((x) >> ((-l) & (31)))) #define _ROTR32_INNER(x, r) (((x) >> (r)) | ((x) << ((-r) & (31)))) #define _ROTL64_INNER(x, l) (((x) << (l)) | ((x) >> ((-l) & (63)))) #define _ROTR64_INNER(x, r) (((x) >> (r)) | ((x) << ((-r) & (63)))) #define ROTR32(x, r) (((r) < (0)) ? (_ROTL32_INNER((x), ((u64)(-r) % (32)))) : (_ROTR32_INNER((x), ((r) % (32))))) #define ROTL32(x, l) ROTR32((x), (-l)) #define ROTR64(x, r) (((r) < (0)) ? (_ROTL64_INNER((x), ((u64)(-r) % (64)))) : (_ROTR64_INNER((x), ((r) % (64))))) #define ROTL64(x, l) ROTR64((x), (-l)) #define BIT_FLOOR32(a) ((a) ? (1u) << MSB32((a)) : (0)) #define BIT_FLOOR64(a) ((a) ? (1ull) << MSB64((a)) : (0)) #define BIT_CEIL32_REF(a) \ do { \ --(a); \ (a) |= (a) >> (1); \ (a) |= (a) >> (2); \ (a) |= (a) >> (4); \ (a) |= (a) >> (8); \ (a) |= (a) >> (16); \ (a)++; \ } while(0); #define BIT_CEIL64_REF(a) \ do { \ --(a); \ (a) |= (a) >> (1); \ (a) |= (a) >> (2); \ (a) |= (a) >> (4); \ (a) |= (a) >> (8); \ (a) |= (a) >> (16); \ (a) |= (a) >> (32); \ (a)++; \ } while(0); i32 in_i32(void) { i32 c, x = 0, f = 1; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; } static inline void out_i32_inner(i32 x) { if (x >= 10) out_i32_inner(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } void out_i32(i32 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } out_i32_inner(x); } i64 in_i64(void) { i64 c, x = 0, f = 1; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; } static inline void out_i64_inner(i64 x) { if (x >= 10) out_i64_inner(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } void out_i64(i64 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } out_i64_inner(x); } u32 in_u32(void) { u32 c, x = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; } void out_u32(u32 x) { if (x >= 10) out_u32(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } u64 in_u64(void) { u64 c, x = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; } void out_u64(u64 x) { if (x >= 10) out_u64(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } void NL(void) { putchar_unlocked('\n'); } void SP(void) { putchar_unlocked(' '); } void dump_i32(i32 x) { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m\n", x); } void dump_i64(i64 x) { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m\n", x); } void dump_u32(u32 x) { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m\n", x); } void dump_u64(u64 x) { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m\n", x); } void dump_i32_array(i32 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m ", a[i]); } } } void dump_i64_array(i64 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m ", a[i]); } } } void dump_u32_array(u32 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m ", a[i]); } } } void dump_u64_array(u64 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m ", a[i]); } } } void dump_i32_array_range(i32 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m ", a[i]); } } } void dump_i64_array_range(i64 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m ", a[i]); } } } void dump_u32_array_range(u32 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m ", a[i]); } } } void dump_u64_array_range(u64 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m ", a[i]); } } } void printb_32bit(u32 v) { u32 mask = (u32)1 << (sizeof(v) * CHAR_BIT - 1); do { putchar_unlocked(mask & v ? '1' : '0'); } while (mask >>= 1); } void printb_64bit(u64 v) { u64 mask = (u64)1 << (sizeof(v) * CHAR_BIT - 1); do { putchar_unlocked(mask & v ? '1' : '0'); } while (mask >>= 1); } int jacobi_symbol(i64 a, u64 n) { u64 t; int j = 1; while (a) { if (a < 0) { a = -a; if ((n & 3) == 3) j = -j; } int s = CTZ64(a); a >>= s; if (((n & 7) == 3 || (n & 7) == 5) && (s & 1)) j = -j; if ((a & n & 3) == 3) j = -j; t = a, a = n, n = t; a %= n; if ((u64)(a) > n / 2) a -= n; } return n == 1 ? j : 0; } /******************************/ /* 64bit montgomery reduction */ /******************************/ static u64 N = 0ul, NI = 0ul, R1 = 0ul, R2 = 0ul; void Montgomery64(u64 n) { N = n; NI = n; for (int _ = 0; _ < 5; ++_) NI *= 2 - NI * n; R1 = (u64)(i64)-1 % n + 1; R2 = (u128)(i128)-1 % n + 1; } u64 mr64(u128 A) { u64 y = (u64)(A >> 64) - (u64)(((u128)((u64)A * NI) * N) >> 64); return (i64)y < 0 ? y + N : y; } u64 To(u64 a) { return mr64((u128)R2 * a); } u64 From(u64 mra) { return mr64((u128)mra); } u64 Add(u64 mra, u64 mrb) { mra += mrb; mra -= (mra >= N ? N : 0); return mra; } u64 Sub(u64 mra, u64 mrb) { mra += (mra < mrb ? N : 0); mra -= mrb; return mra; } u64 Min(u64 mra) { return Sub(0, mra); } u64 Mul(u64 mra, u64 mrb) { return mr64((u128)mra * mrb); } u64 Square(u64 mra) { return mr64((u128)mra * mra); } u64 Twice(u64 mra) { return (mra <<= 1) >= N ? (mra - N) : mra; } u64 Power(u64 mra, u64 k) { u64 ret = R1, a = mra; while (k > 0) { if (k & 1) { ret = Mul(ret, a); } a = Mul(a, a); k >>= 1; } return ret; } u64 Inverse(u64 mra) { return Power(mra, N - 2); } u64 Div(u64 mra, u64 mrb) { return Mul(mra, Inverse(mrb)); } u64 Half(u64 mra) { return (mra & 1) ? ((mra >> 1) + (N >> 1) + 1) : (mra >> 1); } int Equal(u64 mra, u64 mrb) { return (((mra >= N) ? (mra - N) : mra) == ((mrb >= N) ? (mrb - N) : mrb)) ? 1 : 0; } int NotEqual(u64 mra, u64 mrb) { return (((mra >= N) ? (mra - N) : mra) != ((mrb >= N) ? (mrb - N) : mrb)) ? 1 : 0; } u64 In() { u64 c = 0; u64 a = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { a = a * 10 + c - 48; c = getchar_unlocked(); } return To(a); } void Out(u64 mra) { u64 a = From(mra); out_u64(a); } bool baillie_psw(u64 n) { { if (n < 2) return false; if (n < 4) return true; if (!(n & 1)) return false; } Montgomery64(n); { u64 d = (n - 1) << CLZ64(n - 1); u64 t = Twice(R1); for (d <<= 1; d; d <<= 1) { t = Square(t); if (d >> 63) t = Twice(t); } if (t != R1) { u64 x = LSBit(n - 1); u64 rev = Min(R1); for (x >>= 1; t != rev; x >>= 1) { if (x == 0) return false; t = Square(t); } } } { i64 D = 5; for (int i = 0; jacobi_symbol(D, n) != -1 && i < 64; ++i) { if (i == 32) { u64 sqrt_N = (u64)sqrtl((f80)N); return sqrt_N * sqrt_N == N; } if (i & 1) D -= 2; else D += 2; D = -D; } u64 Q = To((D < 0) ? ((1 - D) / 4 % n) : (n - (D - 1) / 4 % n)); u64 u = R1, v = R1, Qn = Q; u64 k = (n + 1) << CLZ64(n + 1); D %= (i64)n; D = To((D < 0) ? (D + n) : D); for (k <<= 1; k; k <<= 1) { u = Mul(u, v); v = Sub(Square(v), Add(Qn, Qn)); Qn = Square(Qn); if (k >> 63) { u64 uu = Add(u, v); uu = Half(uu); v = Half(Add(Mul(D, u), v)); u = uu; Qn = Mul(Qn, Q); } } if (u == 0 || v == 0) return true; u64 x = (n + 1) & ~n; for (x >>= 1; x; x >>= 1) { u = Mul(u, v); v = Sub(Square(v), Add(Qn, Qn)); if (v == 0) return true; Qn = Square(Qn); } } return false; } u64 next_prime(u64 n) { if (n & 1) n += 2; else n += 1; while (!baillie_psw(n)) n += 2; return n; } int main(void) { int Q = in_i32(); while (Q--) { u64 x = in_u64(); out_u64(x); SP(); putchar_unlocked(baillie_psw(x) ? '1' : '0'); NL(); } return 0; }