#include<iostream>
#include<cstdio>

using namespace std;

int main()
{
    int n;
    long long int x;
    int flag;
    long long int m;
    cin >> n;
    for (int i =0; i < n; i++)
    {
        m = 2;
        flag = 0;
        cin >> x;
        while(m * m <= x)
        {
            if (x % m == 0)
            {
                cout << x << " is not prime" << endl;
                flag = 1;
                break;
            }
            m++;
        }
        if (flag == 0)
        {
            cout << x << " is prime" << endl;
        }
    }
    return 0;
}