//Miller-Rabin

//n  prime a -->a^(n-1)===1(mod n) -->fastPowMod(a,n-1,n)==1

//warn: Carmichael/lucky

ll mulModhaoxiangmeiyonghenman(ll a,ll b,ll n){

    ll ans=;

    for(;b;a=(a<<)%n,b>>=)

        if(b&)

            ans=(ans+a)%n;

    return ans;

}

ll mulMod(ll a,ll b,ll n){    //黑科技

    ll ans=(a*b-(ll)((long double)a/n*b+0.5)*n);

    return ans<?ans+n:ans;

}

ll powMod(ll a,ll b,ll n){

    ll ans=;

    for(;b;a=mulMod(a,a,n),b>>=)

        if(b&)

            ans=(ans*a)%n;

    return ans;

}

bool witness(ll a,ll n,ll u,int t){

    ll now=powMod(a,u,n),pre=now;

    for(int i=;i<=t;i++){

        now=mulMod(now,now,n);

        if(now==&&pre!=&&pre!=n-)

            return true;

        pre=now;

    }

    if(now!=) return true;

    return false;

}

bool mrP(ll n){

    if(n<=) return false;

    if(n==) return true;

    if((n&)==) return false;

    ll u=n-;

    int t=;

    while((u&)==) u>>=,t++;  //n-1=2^t *u

    int a[]={,,,,,};   //or random

    for(int i=;i<;i++){

        if(n==a[i]) return true;

        else if(witness(a[i],n,u,t)) return false;

    }

    return true;

}