Sum of Squared Digits

Choose a positive integer, then square each of its digits and add them together. Repeating this operation on the result over and over produces an infinite sequence.

For example, starting from 5 gives the following sequence.

5, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, ...

The interesting part appears right after 58: because $5^2 + 8^2 = 89$, the number 89 shows up again, and from then on the following block keeps repeating.

89, 145, 42, 20, 4, 16, 37, 58

This cycle also appears when starting from other numbers (for example 3, 18, 36, 64, ...).

Some numbers instead reach a cycle that repeats 1. For example, starting from 19 gives:

19, 82, 68, 100, 1, ...

Given two integers, find the minimum possible sum of the lengths of the two sequences up to the point where the same number first appears in both. The length of a sequence is the number of terms from its starting value up to and including that common number.

For example, starting from 61 and 29, the common number 89 can be reached as (61, 37, 58, 89) and (29, 85, 89), so the sum of lengths is $4 + 3 = 7$. Starting from 19 and 100, the common number 100 can be reached as (19, 82, 68, 100) and (100), so the sum of lengths is $4 + 1 = 5$.

The input consists of several test cases. Each test case is given on one line as two integers $A$ and $B$ ($0 < A, B < 10^9$).

The last line contains two zeros and is not processed.

For each test case, print $A$, $B$, and the minimum sum of the lengths of the two sequences on one line, separated by spaces. If no number appears in both sequences, print 0 instead of the minimum.

Every such sequence eventually reaches one of the following two cycles:

• the cycle repeating 89, 145, 42, 20, 4, 16, 37, 58
• the cycle repeating 1

If the two starting numbers reach different cycles, they share no common number, so the answer is 0.