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

public class Solution {

public static void main(String[] args) {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
    Scanner scan= new Scanner(System.in);

    int casos= scan.nextInt();

    for (int i = 0; i < casos; i++) {
        int number= scan.nextInt();

         if(number<=1){
        System.out.println("Not prime");
    }else{
    boolean esPrimo=true;

    for (int j = 2; j <= Math.sqrt(number); j++) {
        if(number%j==0){
            esPrimo=false;
            break;
        }   
    }
    if(!esPrimo){
        System.out.println("Not prime");
    }else{
        System.out.println("Prime");
    }

    }

}
    }

}