시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 67 20 19 31.667%

문제

양의 정수를 하나 고른 뒤, 각 자리수의 제곱의 합을 구한다. 이것을 계속 반복하면, 흥미로운 특징을 가지는 무한 수열을 얻을 수 있다.

가장 처음에 5로 시작했을 때, 다음과 같은 수열을 얻을 수 있다.

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

여기서 가장 흥미로운 특징은 58다음에 나타난다. 52 + 82 = 89로 이 숫자는 이미 수열에 나왔단 수이다. 즉, 58 다음부터 수열은 다음과 같은 구간이 반복해서 나온다. 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)에서 같은 수를 만들 수 있다. 19와 100으로 시작하는 경우에는 (19, 82, 68, 100), (100)으로 같은 수를 만들 수 있다.

입력

입력을 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, A와 B가 주어진다. (0 < A, B < 109)

마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, A와 B를 출력하고, 두 수열의 길이의 합의 최솟값을 출력한다. 만약, 두 수열에서 같은 수가 나타나지 않는다면, 0을 출력한다.

예제 입력 1

89 89
19 100
61 19
0 0

예제 출력 1

89 89 2
19 100 5
61 19 0

힌트

89, 145, 42, 20, 4, 16, 37, 58 사이클

1 사이클

W3sicHJvYmxlbV9pZCI6IjQ4ODEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OTBcdWI5YWNcdWMyMThcdWM3NTggXHVjODFjXHVhY2YxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViOTdjIFx1ZDU1OFx1YjA5OCBcdWFjZTBcdWI5NzggXHViNGE0LCBcdWFjMDEgXHVjNzkwXHViOWFjXHVjMjE4XHVjNzU4IFx1YzgxY1x1YWNmMVx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTVjXHViMmU0LiBcdWM3NzRcdWFjODNcdWM3NDQgXHVhY2M0XHVjMThkIFx1YmMxOFx1YmNmNVx1ZDU1OFx1YmE3NCwgXHVkNzY1XHViYmY4XHViODVjXHVjNmI0IFx1ZDJiOVx1YzlkNVx1Yzc0NCBcdWFjMDBcdWM5YzBcdWIyOTQgXHViYjM0XHVkNTVjIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0Y1x1YzVkMCA1XHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD41LCAyNSwgMjksIDg1LCA4OSwgMTQ1LCA0MiwgMjAsIDQsIDE2LCAzNywgNTgsIC4uLjxcL3A+XHJcblxyXG48cD5cdWM1ZWNcdWFlMzBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1ZDc2NVx1YmJmOFx1Yjg1Y1x1YzZiNCBcdWQyYjlcdWM5ZDVcdWM3NDAgNThcdWIyZTRcdWM3NGNcdWM1ZDAgXHViMDk4XHVkMGMwXHViMDljXHViMmU0LiA1PHN1cD4yPFwvc3VwPiArIDg8c3VwPjI8XC9zdXA+ID0gODlcdWI4NWMgXHVjNzc0IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWM3NzRcdWJiZjggXHVjMjE4XHVjNWY0XHVjNWQwIFx1YjA5OFx1YzY1NFx1YjJlOCBcdWMyMThcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgNTggXHViMmU0XHVjNzRjXHViZDgwXHVkMTMwIFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWQ2Y1x1YWMwNFx1Yzc3NCBcdWJjMThcdWJjZjVcdWQ1NzRcdWMxMWMgXHViMDk4XHVjNjI4XHViMmU0LiA4OSwgMTQ1LCA0MiwgMjAsIDQsIDE2LCAzNywgNTg8XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YzBhY1x1Yzc3NFx1ZDA3NFx1Yzc0MCBcdWIyZTRcdWI5NzggXHVjMjJiXHVjNzkwXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YjNjNCBcdWIwOThcdWQwYzBcdWIwOThcdWIyOTQgXHVjMGFjXHVjNzc0XHVkMDc0XHVjNzc0XHViMmU0LiAoMywgMTgsIDM2LCA2NCwgXHViNGYxXHViNGYxXHViNGYxKTxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWI1YTQgXHVjMjJiXHVjNzkwXHViMjk0IDFcdWI4NWMgXHViYzE4XHViY2Y1XHViNDE4XHViMjk0IFx1YzBhY1x1Yzc3NFx1ZDA3NFx1Yzc3NCBcdWIwOThcdWQwYzBcdWIwOThcdWFlMzBcdWIzYzQgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IDE5XHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU4OFx1Yzc0NCBcdWI1NGNcdWI5N2MgXHVjMGI0XHVkM2I0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cD4xOSwgODIsIDY4LCAxMDAsIDEsIC4uLjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWMxOVx1Yzc0MCBcdWMyMThcdWFjMDAgXHViMDk4XHVjNjJjIFx1YjU0YyBcdWFlNGNcdWM5YzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVkNTY5XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgNjFcdWFjZmMgMjlcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTc0LCAoNjEsIDM3LCA1OCwgPHN0cm9uZz44OTxcL3N0cm9uZz4pXHVjNjQwICgyOSwgODUsIDxzdHJvbmc+ODk8XC9zdHJvbmc+KVx1YzVkMFx1YzExYyBcdWFjMTlcdWM3NDAgXHVjMjE4XHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiAxOVx1YzY0MCAxMDBcdWM3M2NcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAoMTksIDgyLCA2OCwgPHN0cm9uZz4xMDA8XC9zdHJvbmc+KSwgKDxzdHJvbmc+MTAwPFwvc3Ryb25nPilcdWM3M2NcdWI4NWMgXHVhYzE5XHVjNzQwIFx1YzIxOFx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBBXHVjNjQwIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbHQ7IEEsIEIgJmx0OyAxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWI0NTAgXHVhYzFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIEFcdWM2NDAgQlx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YjQ1MCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YjQ1MCBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVhYzE5XHVjNzQwIFx1YzIxOFx1YWMwMCBcdWIwOThcdWQwYzBcdWIwOThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0LCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+ODksIDE0NSwgNDIsIDIwLCA0LCAxNiwgMzcsIDU4IFx1YzBhY1x1Yzc3NFx1ZDA3NDxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2N5Y2xlMS5wbmdcIiBzdHlsZT1cImhlaWdodDozODRweDsgd2lkdGg6Mzg5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+MSBcdWMwYWNcdWM3NzRcdWQwNzQ8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jeWNsZTIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzA1cHg7IHdpZHRoOjI4OHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0ODgxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3VtIHRoZSBTcXVhcmUiLCJkZXNjcmlwdGlvbiI6IjxwPlRha2UgYW55IHBvc2l0aXZlIG51bWJlciwgXHVmYjAxbmQgdGhlIHN1bSBvZiB0aGUgc3F1YXJlcyBvZiBpdHMgZGlnaXRzLCByZXBlYXQhIFlvdSZyc3F1bztsbCBlbmQgdXAgd2l0aCBhbiBpblx1ZmIwMW5pdGUgc2VxdWVuY2Ugd2l0aCBhbiBpbnRlcmVzdGluZyBwcm9wZXJ0eSB0aGF0IHdlIHdvdWxkIGxpa2UgdG8gaW52ZXN0aWdhdGUgZnVydGhlci4gU3RhcnRpbmcgd2l0aCB0aGUgbnVtYmVyIDUsIHRoZSBzZXF1ZW5jZSBpczo8XC9wPlxyXG5cclxuPHA+KDUsMjUsMjksODUsODksMTQ1LDQyLDIwLDQsMTYsMzcsNTgsLi4uKTxcL3A+XHJcblxyXG48cD5UaGUgaW50ZXJlc3RpbmcgcGFydCBpcyBpbiB3aGF0IGNvbWVzIGFmdGVyIDU4OiA1PHN1cD4yPFwvc3VwPiArIDg8c3VwPjI8XC9zdXA+ID0gODkgd2hpY2ggaXMgYSBudW1iZXIgdGhhdCZyc3F1bztzIGFscmVhZHkgYmVlbiBzZWVuIGluIHRoZSBzZXF1ZW5jZS4gSW4gb3RoZXIgd29yZHMsIGFmdGVyIDU4LCB0aGUgc2VxdWVuY2Ugd2lsbCBmYWxsIGludG8gdGhlIHJlcGVhdGluZyBjeWNsZTogODksMTQ1LDQyLDIwLDQsMTYsMzcsNTguPFwvcD5cclxuXHJcbjxwPldoYXQmcnNxdW87cyBhbWF6aW5nIGlzIHRoYXQgdGhpcyBjeWNsZSB3aWxsIGFwcGVhciBmb3IgbWFueSBvdGhlciBudW1iZXJzOiAzLCAxOCwgMzYsIGFuZCA2NCBqdXN0IHRvIG5hbWUgYSBmZXcuIChzZWUgXHVmYjAxZ3VyZSBvbiB0aGUgZm9sbG93aW5nIHBhZ2UuKTxcL3A+XHJcblxyXG48cD5Gb3Igc29tZSBudW1iZXJzLCB0aGUgc2VxdWVuY2Ugd2lsbCBmYWxsIGludG8gYW5vdGhlciByZXBlYXRpbmcgY3ljbGUgYnkgcmVhY2hpbmcgMS4gKHNlZSBzZWNvbmQgXHVmYjAxZ3VyZSBvbiB0aGUgZm9sbG93aW5nIHBhZ2UpIEZvciBleGFtcGxlLCBzdGFydGluZyB3aXRoIDE5LCB5b3UmcnNxdW87bGwgZW5kIHVwIHdpdGggdGhlIHNlcXVlbmNlOjxcL3A+XHJcblxyXG48cD4oMTksODIsNjgsMTAwLDEsLi4uKTxcL3A+XHJcblxyXG48cD5BbmQgdGhhdCZyc3F1bztzIGFib3V0IGl0LiBBbnkgbnVtYmVyIHlvdSBjaG9vc2Ugd2lsbCBlbmQgdXAgZmFsbGluZyBpbnRvIGEgcmVwZWF0aW5nIGN5Y2xlOiBFaXRoZXIgdGhlIDg5LDE0NSwuLi4gY3ljbGUgb3IgdGhlIDEsLi4uIGN5Y2xlLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0d28gbnVtYmVycywgeW91ciBvYmplY3RpdmUgaXMgdG8gZ2VuZXJhdGUgYXMgZmV3IG51bWJlcnMgaW4gdGhlaXIgc2VxdWVuY2VzIGZvciB0aGUgdHdvIHNlcXVlbmNlcyB0byBpbnRlcnNlY3QgYXQgb25lIGNvbW1vbiBudW1iZXIuIEZvciBleGFtcGxlLCBnaXZlbiA2MSBhbmQgMjksIHdlIGNhbiBhY2hpZXZlIHdoYXQmcnNxdW87cyByZXF1aXJlZCBieSBnZW5lcmF0aW5nIHRoZSBzZXF1ZW5jZXM6ICg2MSwzNyw1OCw8c3Ryb25nPjg5PFwvc3Ryb25nPikgYW5kICgyOSw4NSw8c3Ryb25nPjg5PFwvc3Ryb25nPikuIFNpbWlsYXJseSwgZm9yIDE5IGFuZCAxMDAsIHRoZSBzZXF1ZW5jZXMgd291bGQgYmUgKDE5LDgyLDY4LDxzdHJvbmc+MTAwPFwvc3Ryb25nPikgYW5kICg8c3Ryb25nPjEwMDxcL3N0cm9uZz4pLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIHdpbGwgYmUgdGVzdGVkIG9uIG9uZSBvciBtb3JlIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGlzIHNwZWNpXHVmYjAxZWQgb24gYSBzaW5nbGUgbGluZSBoYXZpbmcgdHdvIGludGVnZXJzICgwICZsdDsgQSwgQiAmbHQ7IDEwPHN1cD45PFwvc3VwPikuPFwvcD5cclxuXHJcbjxwPlRoZSBsYXN0IGNhc2UgaXMgZm9sbG93ZWQgYnkgYSBkdW1teSBsaW5lIG1hZGUgb2YgdHdvIHplcm9zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgdGhlIGZvbGxvd2luZyBsaW5lOjxcL3A+XHJcblxyXG48cHJlPlxyXG5BXHUwMDAyIEIgXHUwMDAyUzxcL3ByZT5cclxuXHJcbjxwPldoZXJlIEEsIEIgYXJlIGFzIGluIHRoZSBpbnB1dCBhbmQgUyBpcyB0aGUgKG1pbmltdW0pIHN1bSBvZiB0aGUgbGVuZ3RocyBvZiB0aGUgdHdvIHNlcXVlbmNlcy4gSWYgdGhlIHNlcXVlbmNlcyBzdGFydGluZyBhdCBBIGFuZCBCIGRvIG5vdCBpbnRlcnNlY3QsIHRoZW4gUyA9IDAuPFwvcD5cclxuIiwiaGludCI6IjxwPkZldyBudW1iZXJzIGZhbGxpbmcgaW50byB0aGUgODksMTQ1LDQyLDIwLDQsMTYsMzcsNTggY3ljbGU8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jeWNsZTEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6Mzg0cHg7IG9wYWNpdHk6MC45OyB3aWR0aDozODlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GZXcgbnVtYmVycyBmYWxsaW5nIGludG8gdGhlIDEgY3ljbGUuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY3ljbGUyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjMwNXB4OyB3aWR0aDoyODhweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d