#include<iostream>
#include<cmath>
using namespace std;
int main(){
int n,x,t=1;
cin>>n;
for(int i=0;i<n;i++){
cin>>x;
for(int j=2;j<=sqrt(x);j++){
if (x%j==0){
t=0;
break;
}
else t=1;//这一点自己易忽略啊,其实应该前面不初始化t的,这样这里才不会忘
}
if(t||x==2)//2是一个特例,不要忘了
cout<<x<<" is prime"<<endl;
else
cout<<x<<" is not prime"<<endl;
}
return 0;
}