Let the sum of the square of the digits of a positive integer S₀ be represented by S_1. In a similar way, let the sum of the squares of the digits ofS₁ be represented by S₂ and so on. If S_i = 1 for some i 3 1, then the original integer S₀ is said to be Happy number. A number, which is not happy, is called Unhappy number. For example 7 is a Happy number since 7 -> 49 -> 97 -> 130 -> 10 -> 1 and 4 is an Unhappy number since 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4.

Input

The input consists of several test cases, the number of which you are given in the first line of the input. Each test case consists of one line containing a single positive integer N smaller than 10⁹.

Output

For each test case, you must print one of the following messages:

Case #p: N is a Happy number.

Case #p: N is an Unhappy number.

Here p stands for the case number (starting from 1). You should print the first message if the number N is a happy number. Otherwise, print the second line.

Problemsetter: Mohammed Shamsul Alam

International Islamic University Chittagong

Special thanks to Muhammad Abul Hasan

一道直接可以模拟的哈希的水题，注意happy number的最大值不超过9*81。开的哈希数组1000就够用。

#include<iostream>
#include<cstring>

using namespace  std;

int tag[1000];

int Happy(int num)
{
    int sum=0;
    while(num!=0)
    {
        sum=sum+(num%10)*(num%10);
        num=num/10;
    }
    return sum;
}

int main()
{
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>m;
        memset(tag,0,sizeof(tag));
        int flag=0;
        int s=Happy(m);
        while(tag[s]==0)
        {
            if(s==1)
            {
                flag=1;
                break;
            }
            tag[s]=1;
            s=Happy(s);
        }
        cout<<"Case #"<<i<<": "<<m<<" is";
        if(flag==1) cout<<" a Happy number."<<endl;
        else cout<<" an Unhappy number."<<endl;
    }
    return 0;
}

[哈希&&模拟]Happy Number uva10591