#include <iostream>

using namespace std;

bool isprime(int n) {
    if (n == 1) {
        return false;
    }
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int main(void)
{
    int caseNumber;
    cin >> caseNumber;

    while (caseNumber--) {
        int n;
        cin >> n;
        if (isprime(n)) {
            printf("%d is prime\n", n);
        } else {
            printf("%d is not prime\n", n);
        }
    }



    return 0;
}