Primality Evaluation

In this problem, you are given a list of integers and you need to evaluate whether each integer is a prime number. A number ( n ) is said to be prime if it has exactly two distinct positive divisors: 1 and ( n ) itself. Note that by convention, any number ( n \leq 1 ) is not a prime number.

Your task is to implement the check based on the following criteria:

• If \( n \leq 1 \), then the answer is NOT PRIME.
• If \( n = 2 \), then the answer is PRIME.
• If \( n \) is even and \( n \neq 2 \), it is NOT PRIME.
• Otherwise, check divisibility from 3 to \( \lfloor\sqrt{n}\rfloor \) (stepping by 2). If any divisor is found, output NOT PRIME; otherwise, output PRIME.

The input will be processed from standard input and the output should be printed to standard output.

inputFormat

The input begins with a single integer ( T ) (( 1 \leq T \leq 10^5 )) representing the number of test cases. Following this, there are ( T ) space-separated integers. Each integer ( n ) (( -10^9 \leq n \leq 10^9 )) is to be evaluated for primality.

outputFormat

Output ( T ) lines. Each line should contain either PRIME or NOT PRIME corresponding to the evaluation of each integer from the input.## sample

5
2 4 5 10 11

PRIME
NOT PRIME
PRIME
NOT PRIME
PRIME

</p>