#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>m;
        for (int j = 2; j <= m-1; j ++){
            if(m % j == 0){
                cout<<m<<" "<<"is not prime"<<endl;
                break;
            }
            if(m % j != 0 && j==m-1){
                cout<<m<<" "<<"is prime"<<endl;
            break;
        }
        }
        
        
    }


    return 0;
}