int prime_list[]={2,3,5,11,17,19,23,37,41,43};
int qpow(int x,int y,int z){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%z;
		x=1ll*x*x%z;
		y>>=1;
	}
	return ret;
} 
bool miller_rabin(int n,int a){//O(logn)
	int d=n-1,r=0;
	while(!(d&1))d>>=1,r++;
	//n-1=d*2^r
	int x=qpow(a,d,n);
	if(x==1)return 1;
	for(int i=0;i<r;i++){
		if(x==n-1)return 1;
		x=1ll*x*x%n;
	}
	return 0;
}
bool prime(int n){
	if(n<2)return 0;
	for(int i=0;i<10;i++){
		if(n==prime_list[i])return 1;
		if(!miller_rabin(n,prime_list[i]))return 0;
	}
	return 1;
}