Математики царства Ерудит на своєму щорічному зібранні вирішили, що у них будуть свої прості числа - прості числа царства Ерудит. На відміну від звичних простих чисел, ці числа мають не два, а три різних додатних дільника. Головний радник доповів про це царю. А цар Ерудиту, як ви знаєте, добра людина, тому погодився з таким нововведенням. Але наказав математикам для певних чисел створити таблицю у вигляді 0 та 1, в залежності від того чи є дане число простим числом царства Ерудит, чи ні. Допоможіть математикам. \InputFile У першому рядку вхідного файлу знаходиться одне ціле число \textit{\textbf{N(1 ≤ N ≤ 100 000)}} - кількість чисел, для яких потрібно створити таблицю. Другий рядок містить \textit{\textbf{N}} цілих чисел \textit{\textbf{A_i (1 ≤ A_i ≤ 10^12)}}. \OutputFile У єдиному рядку вихідного файлу повинно міститися послідовність з 0 та 1. 0 -- якщо відповідне число не є простим числом царства Ерудит, та 1 - якщо воно є простим числом царству Ерудит.