ll mulmod(ll a, ll b, ll mod) {
    ll x = 0,y = a % mod;
    while (b > 0) {
        if (b % 2 == 1) {
            x = (x + y) % mod;
        }
        y = (y * 2) % mod;
        b /= 2;
    }
    return x % mod;
}
/*
ll modpow(ll base, ll exponent, ll mod) {
    ll x = 1LL;
    ll y = base;
    while (exponent > 0) {
        cout << x << endl;
        if (exponent % 2 == 1)
            x = (x * y) % mod;
        y = (y * y) % mod;
        exponent = exponent / 2;
    }
    return x % mod;
}
*/
unsigned long long modpow(unsigned long long num, unsigned long long pow, unsigned long long mod)
{
    unsigned long long test;
    unsigned long long n = num;
    for(test = 1; pow; pow >>= 1)
    {
   //     cout << test << " " << n << endl;
        if (pow & 1)
            test = mulmod(test, n, mod);
        n = mulmod(n, n, mod);
    }

    return test; /* note this is potentially lossy */
}

const ll big = 9223372036854775807;
const ll zero = 0LL;
const ll one = 1LL;
const ll two = 2LL;
const ll k[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

bool prime(ll n) {
    if (n < two) {
        return false;
    }
    if (n == 2) {
        return true;
    }
    if (n % two == zero) {
        return false;
    }
    ll s = n - one;
    ll r = zero;
    while (s % two == zero) {
        r += one;
        s /= two;
    }
    ll d = s;
    for (int i = 0; i < 12; i++) {
        if (k[i] > n - two)
            continue;
        ll a = k[i];
        ll x = modpow(a, d, n);
        bool contflag = false;
        if (x == one || x == n - one)
            continue;
        for (int j = 0; j < r - one; j++) {
            x = mulmod(x, x, n);
            if (x == 1)
                return false;
            if (x == n - one) {
                contflag = true;
                break;
            }
        }
        if (contflag)
            continue;
        return false;
    }
    return true;
}