import java.io.*;
import java.util.*;
import java.math.BigInteger;

class Main
{
	public static void main(String args[]) throws Exception
	{
		Scanner cin=new Scanner(System.in);
		
		long a;
		BigInteger bi;
		int t, i;
		
		t = cin.nextInt();
		
		while (t-- > 0)
		{
			a = cin.nextLong();
			bi = BigInteger.valueOf(a);
			if (a == 2 || a == 3 || bi.isProbablePrime(13))
			{
				System.out.println("Prime");
			}
			else
			{
				if (a % 2 == 0)
				{
					System.out.println("2");
					continue;
				}
				for (i = 3; i <= Math.sqrt(a); i += 2)
				{
					if (a % i == 0)
					{
						System.out.println(i);
						break;
					}
				}
			}
		}
	}
}