struct RabinMiller { vector<int> base; RabinMiller() { base = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}; } ll mul_mod(ll x, ll y, ll MOD) { ll res = 0, tmp = x%MOD; while (y > 0) { if (y&1) res = (res + tmp) % MOD; y >>= 1; tmp = (tmp + tmp) % MOD; } return res; } ll pow_mod(ll x, ll exp, ll MOD) { if (exp == 0) return 1; if (x > MOD) x %= MOD; if (exp & 1) { ll half = pow_mod(x, exp >> 1, MOD); return mul_mod(mul_mod(half, half, MOD), x, MOD); } else { ll half = pow_mod(x, exp >> 1, MOD); return mul_mod(half, half, MOD); } } bool primalTest(int a, ll d, ll r, ll n) { ll x = pow_mod(a, d, n); if (x == 1 || x == n-1) return true; x = pow_mod(a, d*r, n); if (x != 1) return false; r >>= 1; while (r>1) { ll m = pow_mod(a, d*r, n); if (m != 1 && m != n-1) return false; if (m == n-1) return true; r >>= 1; } return false; } bool isPrime(ll n) { if (n < 2) return false; if (n < 4) return true; ll d = n - 1; ll r = d&-d; d /= r; for (int a : base) if (a < n && !primalTest(a, d, r, n)) return false; return true; } };