ACPC10B  Sum the Square
Take any positive number, find the sum of the squares of its digits, repeat! You’ll end up with an infinite sequence with an interesting property that we would like to investigate further. Starting with the number 5, the sequence is:
(5, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, . . .)
The interesting part is in what comes after 58: 5^{2} + 8^{2} = 89 which is a number that’s already been seen in the sequence. In other words, after 58, the sequence will fall into the repeating cycle:
89, 145, 42, 20, 4, 16, 37, 58.
What’s amazing is that this cycle will appear for many other numbers: 3, 18, 36, and 64 just to name a few. (see figure on the following page.) For some numbers, the sequence will fall into another repeating cycle by reaching 1. (see second figure on the following page) For example, starting with 19, you’ll end up with the sequence:
(19, 82, 68, 100, 1, . . .)
And that’s about it. Any number you choose will end up falling into a repeating cycle: Either the 89, 145, . . . cycle or the 1, . . . cycle.
Given two numbers, your objective is to generate as few numbers in their sequences for the two sequences to intersect at one common number. For example, given 61 and 29, we can achieve what’s required by generating the sequences: (61, 37, 58, 89) and (29, 85, 89). Similarly, for 19 and 100, the sequences would be (19, 82, 68, 100) and (100).
Input
Your program will be tested on one or more test cases. Each test case is specified on a single line having two integers (0 < A, B < 10^{9} ).
The last case is followed by a dummy line made of two zeros.
Output
For each test case, print the following line:
A B S
Where A, B are as in the input and S is the (minimum) sum of the lengths of the two sequences.
If the sequences starting at A and B do not intersect, then S = 0.
Example
Input:
89 89
19 100
61 19
0 0
Output:
89 89 2
19 100 5
61 19 0
hide comments
Vipul Srivastava:
20160810 16:56:48


poojan :
20160427 07:36:42
Amazing question! Lots of debugging and corner cases!


free mind ;):
20150917 19:56:58
8 month ago i saw this question and today i solved it. Peace.


Eddy Cael:
20150904 03:49:49
This problem is a little suspicious. I challeged to my friend to solve this problem (because I couldn't solve it) He's got AC. Then, I compared the outputs for some test cases... . For example:


:.Mohib.::
20150801 19:55:55
Finally Done... :) 

Mitch Schwartz:
20150205 15:56:42
@Sunil Angadi: It's been years since I looked at this problem, so these comments are general:


Sunil:
20150205 15:00:20
as per prob discussion, for 61 & 29, the answer should be 5 but a program generating ans as 7 gets accepted.

Added by:  Omar ElAzazy 
Date:  20101130 
Time limit:  0.383s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  ACPC 2010 