자리수 제곱의 합

양의 정수를 하나 고른 뒤, 각 자리수를 제곱하여 모두 더한다. 이렇게 얻은 값에 같은 연산을 계속 반복하면 하나의 무한 수열이 만들어진다.

예를 들어 5에서 시작하면 다음과 같은 수열을 얻는다.

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

여기서 흥미로운 점은 58 다음에 나타난다. $5^2 + 8^2 = 89$이므로 89가 다시 등장하고, 그 뒤로는 다음 구간이 계속 반복된다.

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

이 사이클은 다른 수에서 시작해도 나타난다. (예: 3, 18, 36, 64, ...)

한편 어떤 수는 1이 반복되는 사이클에 도달하기도 한다. 예를 들어 19에서 시작하면 다음과 같다.

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

두 정수가 주어질 때, 두 수열에 처음으로 같은 수가 나타날 때까지 필요한 두 수열의 길이의 합의 최솟값을 구하여라. 각 수열의 길이는 시작하는 수부터 그 같은 수까지 포함하는 항의 개수이다.

예를 들어 61과 29에서 시작하면 (61, 37, 58, 89)와 (29, 85, 89)에서 같은 수 89를 만들 수 있고, 길이의 합은 $4 + 3 = 7$이다. 19와 100에서 시작하면 (19, 82, 68, 100)과 (100)에서 같은 수 100을 만들 수 있고, 길이의 합은 $4 + 1 = 5$이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 두 정수 $A$와 $B$가 주어진다. ($0 < A, B < 10^9$)

입력의 마지막 줄에는 0이 두 개 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 한 줄에 $A$, $B$, 그리고 두 수열의 길이의 합의 최솟값을 공백으로 구분하여 출력한다. 두 수열에 공통으로 나타나는 수가 없다면 최솟값 대신 0을 출력한다.

모든 수열은 결국 다음 두 사이클 중 하나에 도달한다.

• 89, 145, 42, 20, 4, 16, 37, 58이 반복되는 사이클
• 1이 반복되는 사이클

두 시작 수가 서로 다른 사이클에 도달하면 공통으로 나타나는 수가 없으므로 답은 0이다.