#include <stdio.h>
#include <math.h>
int main()
{
int t ;
scanf("%d",&t);
for(int cs = 1; cs<=t ; cs++)
{
int n,prime = 1;
scanf("%d",&n);
if(n==1 || n%2 == 0)
{
printf("Not Prime\n");
continue;
}
else if(n==2 || n == 3)
{
printf("Prime\n");
continue;
}
else
{
for(int i = 5 ; i<=sqrt(n) ; i+=2 )
{
if(n%i == 0)
{
printf("Not Prime\n");
prime = 0;
continue;
}
}
}
if(prime)
printf("Prime\n");
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxtYXRoLmg+CgoKaW50IG1haW4oKQp7CiAgICBpbnQgdCA7CiAgICBzY2FuZigiJWQiLCZ0KTsKICAgIGZvcihpbnQgY3MgPSAxOyBjczw9dCA7IGNzKyspCiAgICB7CiAgICAgICAgaW50IG4scHJpbWUgPSAxOwogICAgICAgIHNjYW5mKCIlZCIsJm4pOwoKICAgICAgICBpZihuPT0xIHx8IG4lMiA9PSAwKQogICAgICAgIHsKICAgICAgICAgICAgcHJpbnRmKCJOb3QgUHJpbWVcbiIpOwogICAgICAgICAgICBjb250aW51ZTsKICAgICAgICB9CiAgICAgICAgZWxzZSBpZihuPT0yIHx8IG4gPT0gMykKICAgICAgICB7CiAgICAgICAgICAgIHByaW50ZigiUHJpbWVcbiIpOwogICAgICAgICAgICBjb250aW51ZTsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgZm9yKGludCBpID0gNSA7IGk8PXNxcnQobikgOyBpKz0yICkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYobiVpID09IDApCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgcHJpbnRmKCJOb3QgUHJpbWVcbiIpOwogICAgICAgICAgICAgICAgICAgIHByaW1lID0gMDsKICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGlmKHByaW1lKQogICAgICAgICAgICBwcmludGYoIlByaW1lXG4iKTsKICAgIH0KICAgIAogICAgcmV0dXJuIDA7Cn0K