#include <bits/stdc++.h>
#define MX 10000000
using namespace std;
bool a[MX + 5];
int i , j , n , x;
int main()
{
a[0] = a[1] = true;
for(i = 2;i * i <= MX;i++)
{
if(a[i] == 0)
{
for(j = i * 2;j <= MX;j = j + i)
{
a[j] = true;
}
}
}
scanf("%d",&n);
while(n--)
{
cin >> x;
if (a[x] == 0)
{
cout << x << " is prime" << endl;
}
else
{
cout << x << " is not prime" << endl;
}
}
return 0;
}