Prime Numbers of the Kingdom of Erudite#7406
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 and to indicate whether certain numbers qualify as prime numbers of the Kingdom of Erudit.
Your task is to assist the mathematicians in this endeavor.
The first line of input contains a single integer (1 \leq N \leq 100\,000), representing the number of numbers for which the table needs to be generated. The second line contains integers A_i (1 \leq A_i \leq 10^{12}).
Output a single line containing a sequence of and . For each number, output if it is not a prime number of the Kingdom of Erudit, and if it is.
Example 1