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