#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int n,x,ans;
    cin>>n;
    while(n--){
        cin>>x;
        ans=0;
        for(int i=2;i<=sqrt(x);i++){
            if(x%i==0){
                ans++;
                break;
            }
        }
             if (ans!=0) cout<<x<<" is not prime"<<endl;
            else cout<<x<<" is prime"<<endl;
    }
    return 0;
}