## HPYNOSI - Happy Numbers II - Trial

no tags

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 (12 + 22 + 52) = 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.

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:219204Output:4-11) 19   : 12 + 92 = 822) 82   : 82 + 22 = 683) 68   : 62 + 82 = 1004) 100 : 12 + 02 + 02 = 1The solution for 19 is 4 because we discovered that the integer 19 is happy after we repeated the process 4times.`

#### 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 wecan deduce that if we continue breaking it, the result will never reach 1.
```