You are given $Q$ integers, the $i$-th one being $a_i$. Determine whether they are a prime.

Input

The first line consists of an integer $Q$.
Then, $Q$ lines follow, each line consists of the integer $a_i$.

Output

Output $Q$ lines.
In the $i$-th line, output the answer for $a_i$, which can be either Prime or Not a prime.

Constraints

For all testcases: $1 \le Q \le 10^6, 1 \le a_i \le 10^6$
Subtask 1 (50%): $Q \le 10$
Subtask 2 (50%): No other constraints

Hint

See Sieve of Eratosthenes.