Прості числа царства Ерудит#7406
Математики царства Ерудит на своєму щорічному зібранні вирішили, що у них будуть свої прості числа — прості числа царства Ерудит. На відміну від звичних простих чисел, ці числа мають не два, а три різних додатних дільника.
Головний радник доповів про це царю. А цар Ерудиту, як ви знаєте, добра людина, тому погодився з таким нововведенням. Але наказав математикам для певних чисел створити таблицю у вигляді та , в залежності від того, чи є дане число простим числом царства Ерудит, чи ні.
Допоможіть математикам.
У першому рядку вхідного файлу знаходиться одне ціле число (1 \leq N \leq 100\,000) — кількість чисел, для яких потрібно створити таблицю. Другий рядок містить цілих чисел A_i (1 \leq A_i \leq 10^{12}).
В єдиному рядку вихідного файлу повинна міститися послідовність з та : — якщо відповідне число не є простим числом царства Ерудит, та — якщо воно є простим числом царства Ерудит.
Приклад 1