TEAMBOOK Миллер-Рабин

#include <bits/stdc++.h>
using ld = long double;
#define long long long
#define all(x) x.begin(), x.end()
using namespace std;

long f(__int128 x, long n) {
    return (long)((x * x + 1) % n);
}

__int128 powerMod(__int128 a, long p, __int128 m) {
    a %= m;
    __int128 x = 1;
    for (; p > 0; p >>= 1) {
        if (p & 1) {
            x *= a;
            x %= m;
        }
        a *= a;
        a %= m;
    }
    return x;
}

bool millerRabin(long n) {
    if (n <= 2) {
        return n == 2;
    }
    if (n % 2 == 0) {
        return false;
    }
    if (n <= 40) {
        for (int d = 2; d < n; ++d) {
            if (n % d == 0) {
                return false;
            }
        }
        return true;
    }
    long p = n - 1;
    long q = p;
    while (q % 2 == 0) {
        q /= 2;
    }
    for (long a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        __int128 e = powerMod(a, p, n);
        if (e != 1) {
            return false;
        }
        __int128 x = powerMod(a, q, n);
        vector<__int128> arr;
        while (x != e) {
            arr.push_back(x);
            x *= x;
            x %= n;
        }
        bool have_1 = false;
        bool trash  = false;
        for (auto el : arr) {
            if (el == n - 1) {
                have_1 = true;
            }
        }
        for (auto el : arr) {
            if (el != 1) {
                trash = true;
            }
        }
        if (trash && !have_1) {
            return false;
        }
    }
    return true;
}

bool stupidPrime(long n) {
    if (n < 2) {
        return false;
    }
    for (long d = 2; d * d <= n; ++d) {
        if (n % d == 0) {
            return false;
        }
    }
    return true;
}

long pollard(long n, long x0, int iter) {
    long a = x0, b = x0;
    while (iter--) {
        a = f(a, n);
        b = f(f(b, n), n);
        long d = __gcd(abs(a - b), n);
        if (1 < d && d < n) {
            return d;
        }
    }
    return n;
}

long pollard(long n, int s, int x, int y) {
    for (int d = 2; d <= s; ++d) {
        if (n % d == 0) {
            return d;
        }
    }
    mt19937 rnd;
    uniform_int_distribution<long> randint(0, n - 1);
    while (x--) {
        long x0 = randint(rnd);
        long d = pollard(n, x0, y);
        if (d != n) {
            return d;
        }
    }
    return n;
}

int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#else
    assert(freopen("again.in", "r", stdin));
    assert(freopen("again.out", "w", stdout));
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    long x;
    cin >> x;
    while (cin >> x) {
        if (millerRabin(x)) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    /*
    for (long x = 1; x <= 1000000; ++x) {
        if (stupidPrime(x) != millerRabin(x)) {
            cout << x << " " << stupidPrime(x) << endl;
        }
    }
    */
    return 0;
}