void eulershai(int n){
	NotPrime[1]=1;
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(NotPrime[i]){
			Prime[tot++]=i;
			phi[i]=i-1;
		}
		for(int j=0,k;(k=i*Prime[j])<=n;j++){
			NotPrime[k]=1;
			if(i%Prime[j]==0){
				phi[k]=phi[i]*Prime[j];
				break;
			}
			phi[k]=phi[i]*(Prime[j]-1);
		}
	}
}

void shaifa(int n){
	NotPrime[1]=1;
	for(int i=2;i<=n;i++){
		if(!NotPrime[i]){
			Prime[tot++]=i;
		}
		for(int j=0,k;(k=i*Prime[j])<=n;j++){
			NotPrime[k]=1;
			if(i%Prime[j]==0)break;
		}
	}
}