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