#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        bool prime=true;
        for(int k=2;k<=sqrt(x);k++)
        if(x%k==0){
        prime=false;
            break;
        }
        if(prime)
        printf("%d is prime\n",x);
        else
        printf("%d is not prime\n",x);

    }
        return 0;


}