Miller - Rabin

//Make CSP great again
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
vector<int> Prime = {2, 3, 5, 7, 11, 13, 17, 23};
long long Mul(long long a, long long b, long long mod)
{
    a %= mod;
    b %= mod;
    long long q = (long double)a * b/mod;
    long long r = a * b - q * mod;
    return (r % mod + mod) % mod;
}
long long Pow(long long a, long long b, long long mod)
{
    if (b == 0)
    {
        return 1 % mod;
    }
    long long t = Pow(a, b/2, mod);
    if (b % 2 == 0)
    {
        return Mul(t , t, mod);
    }
    else
    {
        return Mul(Mul(t, t, mod), a, mod);
    }
}
pair<long long, long long> factor(long long a)
{
    long long s = 0;
    while ((a & 1) == 0)
    {
        a >>= 1;
        ++s;
    }
    return {s, a};
}
bool Test(long long s, long long d, long long n, long long witness)
{
    if (n == witness)
    {
        return true;
    }
    long long p = Pow(witness, d, n);
    if (p == 1)
    {
        return true;
    }
    for (; s > 0; -- s)
    {
        if (p == n - 1)
        {
            return true;
        }
        p = Mul(p, p, n);
    }
    return false;
}
bool MillerRabin(long long n)
{
    if (n < 2)
    {
        return false;
    }
    if ((n & 1) == 0)
    {
        return n == 2;
    }
    long long s, d;
    tie(s, d) = factor(n - 1);
    for (int i : Prime)
    {
        if (!Test(s, d, n, i))
        {
            return false;
        }
    }
    return true;
}
void read()
{

}
void solve()
{

}
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   //freopen(TASK".INP", "r", stdin);
   //freopen(TASK".OUT", "w", stdout);
   int t = 1;
   bool typetest = false;
   if (typetest)
   {
      cin >> t;
   }
   for (int __ = 1; __ <= t; ++ __)
   {
      cerr << "Case " << __ << ":" << '\n';
      read();
      solve();
   }
}