isitpriming

Is it Priming?

I am trying to do my homework on identifying prime numbers, but I do not know which of these N numbers I have are prime! Can you help me identify them?

Input

The first line of input contains 1 integer, N.

The following line contains N integers, representing the i-th integer.

Output

For each integer, output "1" (without the quotations) if it is a prime number, and "0" otherwise. Each number should be separated by a space.

Limits

1 <= N < 1000000

0 <= N[i] < 1000000

Test Cases

Sample Input 1

5
2 3 5 8 9

Sample Output 1

1 1 1 0 0

hi guys this is my first problem :D