#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <memory>
#include <stdexcept>
#include <string>
using namespace std;

std::string exec(const string &cmd) {
    char buffer[128];
    std::string result = "";
    std::shared_ptr<FILE> pipe(popen(cmd.c_str(), "r"), pclose);
    if (!pipe) throw std::runtime_error("popen() failed!");
    while (!feof(pipe.get())) {
        if (fgets(buffer, 128, pipe.get()) != NULL)
            result += buffer;
    }
    return result;
}

int main() {
    const string pre = "factor ";
    string line;
    getline(cin, line); // skip count line
    while (getline(cin, line)) {
        bool prime = exec(pre + line).size() == (2 * line.size() + 3);
        cout << (prime ? "Prime" : "Not prime") << endl;
    }
}