int t;
scanf("%d", &t);
int n;
for(int i = 0 ; i < t ; i++){
    scanf("%d", &n);
    if((n % 2 == 0 && n != 2) || n == 1){
        printf("Not prime\n");
    }
    else{
        int isPrime = 1;
        for(int i = 3 ; i <= n/2 ; i+=2){
            if(n % i == 0){
                isPrime = 0;
                break;
            }
        } 
        if(isPrime)
            printf("Prime\n");
        else
            printf("Not prime\n");
    }
}

static boolean isPrime(int n){
        if(n==2 || n==3 )
            return true;
            
        if(n<=1 || n%2==0 || n%3==0)
            return false;
         
        for(int i=5;i*i<=n;i+=6){
            if(n%i==0 || n % (i + 2) == 0)
                return false;
        }
        return true;
    }

import java.io.*;
import java.util.*;

public class Solution {
    
        public static boolean isPrime(int num){
        if (num == 1) return false;
        for (int i = 2; i <= Math.sqrt(num); i++){
            if (num % i == 0) return false;
        } return true;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0){
            int num = sc.nextInt();
            if (isPrime(num)) System.out.println("Prime");
            else System.out.println("Not Prime"); 
        }
        sc.close();
    }
}

import math
t = int(input())
def isPrime(n):
    if n==1: return 'Not prime'
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            return 'Not prime'
    return 'Prime'
for i in range(t):
    n = int(input())
    print(isPrime(n))

const data = input.split(/[\n]/g);
    data.shift();
    data.forEach(e => {
        e = parseInt(e);
       let isPrime = true;
       if(e == 1) return console.log("Not prime");
       for(i = 2; i < e; i++) {
           if(e % i == 0) {
               isPrime = false;
               break;
           }
       } 
       if(isPrime) console.log("Prime");
       else console.log("Not prime");
    });