int main() {
    int T;
    scanf("%d%*c", &T);
    
    if (T > 0) {
        int array[T];
        for (int i = 0; i < T; i++) scanf("%d%*c", &array[i]); 
        for (int i = 0; i < T; i++) {
            int prime = array[i] > 1;
            for (int j = 3; prime && j < array[i]; j += 2) 
                if (array[i] % 2 == 0 || array[i] % j == 0) prime = 0;
            printf("%s\n", prime ? "Prime" : "Not prime");
        }
    }
    
    return 0;
}