import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Main{

    static int MAX = 10000000;

    static boolean sieve[] = new boolean[MAX+5];

    static void calculatePrimes() {
        sieve[0] = sieve[1] = true;
        int i;
        for (i = 2; i * i <= MAX; ++i) {
            if (!sieve[i]) {

                for (int j = i * i; j <= MAX; j += i) {
                    sieve[j] = true;
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner();
        PrintWriter pr = new PrintWriter(System.out);
        calculatePrimes();
        String  cas=sc.next();

        int casos= Integer.parseInt(cas);
        while (casos>0) {

            String numero = sc.next();

            boolean verdad = true;

            for (int i = 0; i < numero.length(); i++) {
                String numer = "";

                int numEntero = Integer.parseInt( numero);

                if (sieve[numEntero]==false) {
                    verdad = true;

                } else {
                    verdad = false;
                    break;
                }
            }
            if (verdad) {
                pr.println("Prime");

            } else {
                pr.println("Not Prime");

            }
            pr.flush();
            casos--;

        }
        pr.close();
    }

    static class Scanner {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        int spaces = 0;

        public String nextLine() throws IOException {
            if (spaces-- > 0) {
                return "";
            } else if (st.hasMoreTokens()) {
                return new StringBuilder(st.nextToken("\n")).toString();
            }
            return br.readLine();
        }

        public String next() throws IOException {
            spaces = 0;
            while (!st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
            return st.nextToken();
        }

        public boolean hasNext() throws IOException {
            while (!st.hasMoreTokens()) {
                String line = br.readLine();
                if (line == null) {
                    return false;
                }
                if (line.equals("")) {
                    spaces = Math.max(spaces, 0) + 1;
                }
                st = new StringTokenizer(line);
            }
            return true;
        }
    }
}