#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;

    while (n--) {
        int t;
        bool flag = false;
        cin >> t;
        for (int i = 2; i * i <= t; i++) {
            if (t % i == 0) {
                flag = true;
                break;
            }
        }
        if (flag) cout << t << " is not prime" << endl;
        else cout << t << " is prime" << endl;
    }
    return 0;
}