Во время отдыха возле озера, Тигра любит писать на песке числа. Потом для каждого из этих чисел находит сумму квадратов цифр, с полученным новым числом операция нахождения суммы повторяется. Если во время вычислений Тигра получал число \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} -- "счастливое".