#include<cstdio>
#include<iostream>

using namespace std;

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

    while(n --)
    {
        int x;
        bool is_prime = true;
        cin >> x;

        for(int i = 2;i * i<= x;i ++) //此处<=，“=”不能少，如6*6=36，19*19=361
            if(x % i == 0 ) is_prime = false;

        if(is_prime) cout << x << " is prime" << endl;
        else cout << x << " is not prime" << endl;
    }
    return 0;
}