Prime Number Checker

Given a sequence of integers, determine whether each number is prime.

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In other words, an integer \(n\) is prime if and only if \(n > 1\) and for every integer \(k\) with \(2 \le k \le \sqrt{n}\), \(k\) does not divide \(n\).

Your task is to read an integer \(N\) representing the count of numbers, followed by \(N\) space-separated integers. For each integer, output "Prime" if the number is prime, or "Not Prime" otherwise.

Example: For the input
4 2 10 7 15
the output should be:
Prime Not Prime Prime Not Prime

inputFormat

The first line contains a single integer \(N\) indicating the number of integers.

The second line contains \(N\) space-separated integers.

Input is read from standard input.

outputFormat

Output exactly \(N\) strings separated by a single space. Each string should be "Prime" if the corresponding integer is prime, or "Not Prime" otherwise.

Output the result to standard output.

## sample

1
2

Prime