Prime Number Checker

You are given a list of integers. For each integer, determine whether it is a prime number or not. A number \( n \) is prime if and only if \( n>1 \) and it has no positive divisors other than 1 and itself, i.e. it is not divisible by any integer from 2 to \( \sqrt{n} \). Print "Prime" for prime numbers and "Not Prime" for non-prime numbers.

The input is provided via standard input (stdin) and the output should be printed to standard output (stdout), one result per line corresponding to each integer’s primality.

inputFormat

The first line contains a single integer \( T \) which denotes the number of test cases. The second line contains \( T \) space-separated integers. \( T \geq 1 \).

Example:

5
2 4 5 9 13

outputFormat

For each integer, output a single line with the string "Prime" if the number is prime, and "Not Prime" otherwise.

Example Output:

Prime
Not Prime
Prime
Not Prime
Prime

## sample

5
2 4 5 9 13

Prime
Not Prime
Prime
Not Prime
Prime

</p>