#include <cstdio>
int main() {
int n;
scanf("%d", &n);
while (n -- ) {
int x;
bool sign = true;
scanf("%d", &x);
for (int i = 2; i * i <= x; i ++ )
if (x % i == 0) sign = false;
if (sign) printf("%d is prime\n", x);
else printf("%d is not prime\n", x);
}
return 0;
}