#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;
}

#include<bits/stdc++.h> using namespace std; int main(){ int n; int a; cin >> n; for (int i = 0;i < n;i++){ cin >> a; bool f = true; for (int j = 2;j < a;j++){ if (a % j == 0){ f = false; } } if (f){ cout << a << " is prime" << endl; }else { cout << a << " is not prime" << endl; } } return 0; }