Q10591: Happy Number

讓我們定義正整數S₀中每個數字的平方和為S₁。以相同的方法我們定義S₁中每個數字的平方和為S₂，並依此類推。假如有某個S_i = 1（ i >= 1）則我們說S₀是一個Happy number。如果某一個數不是Happy number，那他就是一個 Unhappy number。

例如： 7 是一個 Happy number，因為 7 -> 49 -> 97 ->130 -> 10 -> 1。

但是 4 是一個Unhappy number，因為 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4，永遠也無法產生  1。

Input

輸入的第一列有一個整數代表以下有多少組測試資料。

每組測試資料一列含有1個正整數N（ N < 10⁹）。

Output

對每組測試資料輸出一列，輸出這是第幾組測試資料，以及N為 Happy number 或 Unhappy number。輸出格式請參考Sample Output。