During the rest near the lake, Tiger likes to write numbers on the sand. Then, for each of these numbers finds the sum of numbers of the squares, with new given number the operation of sum foundation is repeated. If during the calculation Tiger got the number \textbf{1}, then these numbers it called "happy", and all the rest - "unhappy". Because of Tiger on the sand wrote \textbf{N} numbers, so it asks you to help it to determine which numbers are "happy". \InputFile In the first line is written an integer \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^5}) - the quantity of written numbers, on the second line is written \textbf{N} numbers with space, each of them does not exceed \textbf{2}^\{63 \} and no less than \textbf{0}. \OutputFile To put out in one line \textbf{N} numbers \textbf{0} or \textbf{1} without separating spaces, where \textbf{0} means "unlucky" number, and \textbf{1} - "happy".