The process of “breaking” an integer is defined as summing the squares of its digits. For example, the result of breaking the integer 125 is (1² + 2² + 5²) = 30. An integer N is happy if after “breaking” it repeatedly the result reaches 1. If the result never reaches 1 no matter how many times the “breaking” is repeated, then N is not a happy number.

TASK

Write a program that given an integer T (number of test cases) and T integers, determines for each number whether it is a happy number or not.

CONSTRAINTS

1 ≤ T ≤ 1,080,000

2 ≤ N ≤ 2,147,483,647 (number for determining whether it is happy or not)

Input

The first line contains an integer T.

Next 1...T lines contain an integer N for detemining whether it is happy or not.

Output

T lines containing a single integer N which is the number of times the process had to be done to determine that N is happy, or -1 if N is not happy.

Example

Input:
2
19
204

Output:
4
-1

1) 19  : 12 + 92 = 82
2) 82  : 82 + 22 = 68
3) 68  : 62 + 82 = 100
4) 100 : 12 + 02 + 02 = 1

The solution for 19 is 4 because we discovered that the integer 19 is happy after we repeated the process 4 times.

204 –> 20 –> 4 –> 16 –> 37 –> 58 –> 89 –> 145 –> 42 –> 20 –> 4 –> 16 –> 37 –> 58 –> 89 –> 145 ……

204 is not a happy number because after breaking it several times the results start repeating so we can deduce that if we continue breaking it, the result will never reach 1.