beecrowd | 1221

Fast Prime Number

By Neilor Tonin, URI Brazil

Timelimit: 1

Mary knows that a Prime Number is a number that is divisible only by 1 (one) and by itself. For example the number 7 is Prime, because it can be divided only by 1 and by 7. So she asked you to write a program that reads many numbers ​​and inform if each one of these numbers are prime or not. But Patience is not one of the virtues of Mariazinha, so she wants that the execution of all test cases (instances) created by herself happen at the maximum in one second, because she hates waiting :>).

Input

The first input line contains an integer N (1 ≤ N ≤ 200), corresponding to the number of test cases. Follow N lines, each one containig one integer number X (1 < X < 231) that can be or not a prime number

Output

For each test case output the message “Prime” or “Not Prime” according to the to following example.

Sample Input Sample Output

3
123321
123
103

Not Prime
Not Prime
Prime