#include<iostream>
#include<cstdlib>
int Pow(long long x,int n,long long mod) {
    long long Ans=1,t=x;
    while(n){
        if(n&1)Ans*=t,Ans%=mod;
        t*=t,t%=mod,n>>=1;
    }
    return (int)Ans;
}
int JudgePrime(int n) {
    if(n==2||n==3)return 1;
    else if(n==1)return 0;
    else if(!(n&1))return 0;
    int a,x,t;
    for(a=0;a<2;a++){
        x=rand()%(n-4)+2;
        t=Pow(x,n-1,n);
        if(t!=1)return 0;
    }
    return 1;
}
//a007 AC code
//using Miller Rabin Algorithm