eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Прості числа царства Ерудит

Прості числа царства Ерудит

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Математики царства Ерудит на своєму щорічному зібранні вирішили, що у них будуть свої прості числа - прості числа царства Ерудит. На відміну від звичних простих чисел, ці числа мають не два, а три різних додатних дільника.

Головний радник доповів про це царю. А цар Ерудиту, як ви знаєте, добра людина, тому погодився з таким нововведенням. Але наказав математикам для певних чисел створити таблицю у вигляді 0 та 1, в залежності від того чи є дане число простим числом царства Ерудит, чи ні.

Допоможіть математикам.

Входные данные

У першому рядку вхідного файлу знаходиться одне ціле число N(1 ≤ N ≤ 100 000) - кількість чисел, для яких потрібно створити таблицю. Другий рядок містить N цілих чисел A_i (1 ≤ A_i ≤ 10^12).

Выходные данные

У єдиному рядку вихідного файлу повинно міститися послідовність з 0 та 1. 0 – якщо відповідне число не є простим числом царства Ерудит, та 1 - якщо воно є простим числом царству Ерудит.

Пример

Входные данные #1
2
3 4
Выходные данные #1
01
Источник ACM-ICPC Ukraine 2015, Перший етап Україна, 25 квітня 2015 року