Happy Numbers

Let the sum of the squares of the digits of a positive integer s₀ be represented by s₁. In a similar way, let the sum of the squares of the digits of s₁ be represented by s₂, and so on. If s_i=1 for some i>=1, then the original integer s₀ is said to be happy. For example, starting with 7 gives the sequence

7, 49 (=7^2), 97 (=4^2+9^2), 130 (=9^2+7^2), 10 (=1^2+3^2), 1 (=1^2),

so 7 is a happy number.

The first few happy numbers are 1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97, 100, .... The number of iterations i required for these to reach 1 are, respectively, 1, 6, 2, 3, 5, 4, 4, 3, 4, 5, 5, 3, ....

A number that is not happy is called unhappy. Once it is known whether a number is happy (unhappy), then any number in the sequence s₁, s₂, s₃, ... will also be happy (unhappy). Unhappy numbers have eventually periodic sequences of s_i which do not reach 1 (e.g., 4, 16, 37, 58, 89, 145, 42, 20, 4, ...).

Any permutation of the digits of a happy (unhappy) number must also be happy (unhappy). This follows from the fact that addition is commutative. Moreover, the product of a happy (unhappy) number by any power of ten is a happy (unhappy) number. Example: 58 is an unhappy number; then, so are 85, 580, 850, 508, 805, 5800, 5080, 5008, 8050, 8500, and so on.

Problem

Decide which numbers, in a given closed interval, are happy numbers.

Input

The input has n lines each of them corresponding to a test case. Every line contains two positive integers between 1 and 99999 (inclusive) each; the first integer, L, is the low limit of the closed interval; the second one, H, is the high limit (L ≤ H).

Output

The output is composed of the happy numbers that lie in the interval [L,H], together with the number of iterations required for the corresponding sequences of squares to reach 1.

There must be a line for each happy number containing the happy number followed by a space and the number of iterations required for the sequence of squares to reach 1.

Print a blank line between two consecutive test cases.

Sample Input

5 28
233 250

Sample Output

7 6
10 2
13 3
19 5
23 4
28 4

236 6
239 6

#include <stdio.h>
#include <set>
using namespace std;
int happy[100000] = {};
void solve() {
    int i;
    for(i = 1; i < 100000; i++) {
        int l = 0, n = i, tmp;
        set<int> s;
        while(n != 1) {
            l++;
            tmp = 0;
            while(n) {
                tmp += (n%10)*(n%10);
                n /= 10;
            }
            n = tmp;
            if(s.find(n) != s.end())
                break;
            s.insert(n);
        }
        if(n == 1)
            happy[i] = l+1;
    }
}
int main() {
    solve();
    int flag = 0, L, H;
    while(scanf("%d %d", &L, &H) == 2) {
        if(flag)
            puts("");
        flag = 1;
        for(int i = L; i <= H; i++) {
            if(happy[i])
                printf("%d %d\n", i, happy[i]);
        }
    }
    return 0;
}