#include <iostream>
using namespace std;
int main() {
int n, x;
cin >> n;
for (int i = 0; i < n; i++){
cin >> x;
for (int j = 2; j <= x / j; j++) {
if (x % j == 0){
cout << x << " is not prime" << endl;
break;
}
if (j == x / j || j == x / j - 1){
cout << x << " is prime" << endl;
}
}
if (x == 2){
cout << x << " is prime" << endl;
}
}
return 0;
}