Під час відпочинку біля озера, Тигра полюбляє писати на піску числа. Потім для кожного з цих чисел знаходить суму квадратів цифр, з отриманим новим числом операція знаходження суми повторюється. Якщо під час обчислення Тигра отримував число \textbf{1}, то такі числа він називав "щасливими", а всі інші -- "нещасливими". Оскільки на піску Тигра написав \textbf{N} чисел, то він просить Вас допомогти йому визначити, які з чисел "щасливі". \InputFile У першому рядку записано ціле число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^5}) -- кількість написаних чисел, у другому рядку через пропуски записано \textbf{N} чисел, кожне з яких не перевищує \textbf{2}^\{63 \}і не менше ніж \textbf{0}. \OutputFile Вивести у одному рядку \textbf{N} чисел \textbf{0} або \textbf{1} без розділяючих пропусків, де \textbf{0} позначає "нещасливе" число, а \textbf{1} -- "щасливе".