#include<iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;

    while(n--)
    {
        int x;
        cin>>x;

        bool is_prime=true;

        for(int i=2;i*i<=x;i++)   //此题要进行优化
        if(x%i==0)
        {
            is_prime=false;
            break;
        }
        if(is_prime) cout<<x<<" is prime"<<endl; //注意 if括号内对is prime 判断的写法
        else  cout<<x<<" is not prime"<<endl;

    }
    return 0;
}