[模板] miller

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

ll (ll a, ll b, ll mod) {
    return __int128(a)*__int128(b)%mod;
}

ll qpow(ll a, ll x, ll mod) {
    ll ret = 1;
    while (x) {
        if (x & 1) ret = mul(ret, a, mod);
        a = mul(a, a, mod);
        x >>= 1;
    }
    return ret;
}

int prm[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

ll miller_rabin(ll p) {
    if (p == 2) return 1;
    if (p == 1 || p % 2 == 0) return 0;
    ll t = p-1, c = 0;
    while (t % 2 == 0) {
        t /= 2;
        ++ c;
    }
    for (int i = 0; i < 12 && prm[i] < p; i++) {
        int a = prm[i];
        ll v = qpow(a, t, p);
        for (int j = 0; j < c; j++) {
            ll nv = mul(v, v, p);
            if (nv == 1 && v != 1 && v != p-1) return 0;
            v = nv;
        }
        if (v != 1) return 0;
    }
    return 1;
}

int T;

int main() {
    ll n;
    while (scanf("%lld", &n) != EOF) {
        if (miller_rabin(n)) puts("Y");
        else puts("N");
    }
    return 0;
}