using u64 = uint64_t;
using u128 = __uint128_t;
u64 power(u64 a, u64 b, u64 m) {
u64 res = 1;
a %= m;
while (b > 0) {
if (b & 1) res = (u128)res * a % m;
a = (u128)a * a % m;
b >>= 1;
}
return res;
}
bool isPrime(u64 n) {
if (n < 2) return false;
u64 d = n - 1;
int s = 0;
while (d % 2 == 0) d /= 2, s++;
for (u64 a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
if (n % a == 0) return n == a;
u64 x = power(a, d, n);
if (x == 1 || x == n - 1) continue;
bool ok = false;
for (int r = 1; r < s; r++) {
x = (u128)x * x % n;
if (x == n - 1) { ok = true; break; }
}
if (!ok) return false;
}
return true;
}







