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