Let the sum of the squares of the digits of a positive integer s0 be represented by s1. In a similar way, letthesumofthesquaresofthedigitsofs1 berepresentedbys2,andsoon. Ifsi =1forsomei≥1, then the original integer s0 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 s1, s2, s3, . . . will also be happy (unhappy). Unhappy numbers have eventually periodic sequences of si 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. Decide which numbers, in a given closed interval, are happy numbers. Input The input has n lines each of them corresponding to test case. Every line contains two positive integers between 1 and 99999 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. Note: The definition of happy numbers is from MathWorld - http://mathworld.wolfram.com/ Sample Input 5 28 233 250 Sample Output 76 10 2 13 3 19 5
2/2 23 4 28 4 236 6 239 6