Простые числа царства Эрудит
Математики царства Эрудит на ежегодном собрании решили ввести свои собственные простые числа, которые они назвали простыми числами царства Эрудит. В отличие от обычных простых чисел, такие числа имеют три различных положительных делителя.
Главный советник сообщил об этом царю. Царь Эрудита, будучи добрым человеком, одобрил это нововведение. Однако он поручил математикам создать таблицу, содержащую 0 и 1, для определённых чисел, чтобы указать, является ли каждое из них простым числом царства Эрудит.
Помогите математикам выполнить это задание.
Входные данные
Первая строка входного файла содержит одно целое число N (1 ≤ N ≤ 100 000) — количество чисел, для которых необходимо создать таблицу. Вторая строка содержит N целых чисел A[i] (1 ≤ A[i] ≤ 10^{12}).
Выходные данные
В единственной строке выходного файла должна быть последовательность из 0 и 1. 0 указывает, что соответствующее число не является простым числом царства Эрудит, а 1 — что является.