#include<cstdio>
#include <cmath>

#define MAXN 10000005
using namespace std;

bool composto[MAXN];

void crivo()
{
    composto[1] = 1;
    for(int i = 2; i<=sqrt(MAXN); ++i)
    {
        if(!composto[i])
        {
            for(int j = i*i; j<=MAXN; j+=i)
            {
                composto[j] =1;
            }
        }
    }
}

int main()
{
    crivo();

    int n, a;
    scanf("%d", &n);
    while(n--)
    {
        scanf("%d", &a);
        if(composto[a])
            printf("%d nao eh primo\n", a);
        else
            printf("%d eh primo\n", a);
    }

    return 0;
}