RM

ll R[]={2,3,5,7,11,13,17,19,23,29,31,37};
ll mm(ll a,ll b,ll M){
    ll v(0),w(a%M);
    while(b)v=b&1?(v+w)%M:v,w=(w<<1)%M,b>>=1;
    return v%M;
}
ll pw(ll n,ll k,ll M){
    ll r=1;
    while(k){
        if(k&1)r= mm(r,n,M);
        n=mm(n,n,M),k>>=1;
    }
    return r%M;
}
bool isP(ll n){
    if(n<2)return 0;
    if(!(n&1))return n==2;
    ll s=n-1;
    while(!(s&1))s>>=1;
    if(n<40){FT(3,n)if(!(n%k))return 0;return 1;}
    F(12){
        ll z(R[i]),t(s),r(pw(z,t,n));
        if(r==1||!~r==-1)continue;
        while(t!=n-1&&r!=n-1)
            r=mm(r,r,n),t<<=1;
        if(r!=n-1)return 0;
    }
    return 1;
}