Prime Numbers of the Kingdom of Erudite
At the annual gathering of the mathematicians in the Kingdom of Erudit, they decided to define a special category of prime numbers unique to their kingdom. Unlike traditional prime numbers, which have exactly two distinct positive divisors, the prime numbers of the Kingdom of Erudit have exactly three distinct positive divisors.
The chief advisor conveyed this decision to the king. Being a benevolent ruler, the King of Erudit embraced this innovation. He instructed the mathematicians to compile a table using 0s and 1s to indicate whether certain numbers qualify as prime numbers of the Kingdom of Erudit.
Your task is to assist the mathematicians in this endeavor.
Input
The first line of input contains a single integer N (1 ≤ N ≤ 100,000), representing the number of numbers for which the table needs to be generated. The second line contains N integers A[i] (1 ≤ A[i] ≤ 10^{12}).
Output
Output a single line containing a sequence of 0s and 1s. For each number, output 0 if it is not a prime number of the Kingdom of Erudit, and 1 if it is.