Щасливе число Тигри

Під час відпочинку біля озера, Тигра полюбляє писати на піску числа. Потім для кожного з цих чисел знаходить суму квадратів цифр, з отриманим новим числом операція знаходження суми повторюється. Якщо під час обчислення Тигра отримував число 1, то такі числа він називав "щасливими", а всі інші – "нещасливими".

Оскільки на піску Тигра написав N чисел, то він просить Вас допомогти йому визначити, які з чисел "щасливі".

Вхідні дані

У першому рядку записано ціле число N (1 ≤ N ≤ 10^5) – кількість написаних чисел, у другому рядку через пропуски записано N чисел, кожне з яких не перевищує 2^{63 }і не менше ніж 0.

Вихідні дані

Вивести у одному рядку N чисел 0 або 1 без розділяючих пропусків, де 0 позначає "нещасливе" число, а 1 – "щасливе".

Приклади