using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        
        int t = int.Parse(Console.ReadLine());
        List<int> possiblePrimes = new List<int>();
        for(int i = 0; i < t; i++)
        {
            possiblePrimes.Add(int.Parse(Console.ReadLine()));
        }
        
        foreach(int p in possiblePrimes)
        {
            string isPrime = "Prime";
            if(p == 1 || (p % 2 == 0 && p != 2))
                isPrime = "Not prime";
            else
            {
                int startAt = (int)Math.Sqrt(p);
                for(int i = startAt; i > 2; i--)
                {
                    if(i % 2 == 0)
                        continue;
                    else if(p % i == 0)
                    {
                        isPrime = "Not prime";
                        break;
                    }
                }
            }
            
            Console.WriteLine(isPrime);
        }
    }
}