Pime is a curious boy who loves prime numbers. Today he wants to play, and gives you \(Q\) random integers. For each of the numbers \(a_{i}\), output true if it is prime, or false if not.

Note: prime numbers are natural numbers only divisible by 1 and by the number itself. 0 and 1 are not considered prime numbers!

Constraints

\(1 \le Q \le 10 ^ 5\)

\(0 \le a_{i} \le 10 ^ 4\)

Input Specification

The first line of input consists of the integer \(Q\), representing the total number of querries.

The next \(Q\) lines each consist of one integer \(a_{i}\), each representing a number given by Pime.

Output Specification

For each of the \(Q\) integers \(a_{i}\), output true if it is prime, or false otherwise. Each answer is to be separated by a new line.

Sample Input

6
3 
5 
1 
0 
8 
7

Sample Output

true
true
false
false
false
true

Explanation for Sample Output

There are \(Q\)=6 numbers in total:

Number 3 is prime, so we output true

Number 5 is prime, so we output true

Number 1 is not prime, so we output false

Number 0 is not prime, so we output false

Number 8 is not prime, so we output false

Number 7 is prime, so we output true