int __p[9]={2,3,5,7,11,13,17,37,87};
int ksm(long long a,long long b,int mod)
{
	long long res=1,ans=a%mod;
	while(b)
	{
		if(b&1)res=res*ans%mod;
		ans=ans*ans%mod;
		b>>=1;
	}
	return res%mod;
}
bool slow_check(int n)
{
	if(n<2)return 0;
	if(n==2||n==3)return 1;
	if(n%2==0)return 0;
	if(n%6!=1&&n%6!=5)return 0;
	for(int i=5;i*i<=n;i+=6)
	{
		if(n%i==0||n%(i+2)==0)return 0;
	}
	return 1;
}
bool _miller_rabin(int n,int a)
{
	int d=n-1,r=0;
	while(d%2==0){d>>=1;r++;}
	int z=ksm(a,d,n);
	if(z==1||z==n-1)return 1;
	while(r--){z=1ll*z*z%n;if(z==n-1)return 1;}
	return 0;
}
bool prime_check(int n)
{
	if(n<2)return 0;
	if(n==2||n==3)return 1;
	if(n%2==0)return 0;
	if(n<=87) return slow_check(n);
	for(int a=0;a<9;a++)
	{
		if(n==__p[a])return 1;
		if(n%__p[a]==0)return 0;
		if(!_miller_rabin(n,a))return 0;
	}
	return 1;
}