Given ~T~ ~(1 \le T \le 100)~ positive integers, one per line, determine whether each one is prime. The integers will be no greater than ~2^{63}-1~.

The first line of input will be the integer ~T~. The next ~T~ lines each contain a number to be tested.

For each of the ~T~ integers, you should output on a separate line PRIME if the corresponding integer is prime, or NOT if it is not prime.

Sample Input

5
1
2
6
11
1000000000000000000

Sample Output

NOT
PRIME
NOT
PRIME
NOT