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

i*i<=n,需要取等是因为n可能能开平方