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

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

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

Вхідні дані:

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

Вихідні дані:

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