시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 18 14 11 73.333%

문제

다음 순열에서 이어지는 항은 무엇일까?

1, 11, 21, 1211, 111221, ...

규칙은 이러하다. 어떤 항이 있을 때 다음 항을 만드는 방법은 현재 항을 같은 숫자들로 구분되도록 쪼갠 후, 각 숫자가 반복되는 횟수를 앞에 붙이는 것이다. 예를 들어 21은 "한 개의 2, 한 개의 1"이므로 다음 항은 1211이 된다. 이와 같은 규칙에 따라서 111221 뒤에는 312211이 오게 된다(세 개의 1, 두 개의 2, 한 개의 1).

다음 항뿐 아니라 이전 항도 알아낼 수 있다. 2221은 그 자체로 "두 개의 2, 두 개의 1"이 있었다는 뜻이므로 이전 항은 2211이다. 또한 2211의 이전 항도 221임을 알 수 있다. 그런데 221의 이전 항은 존재하지 않는다. 왜냐면 이 값을 정보로 나타낼 수 있는 수가 없기 때문이다. 또한 2212도 이전 항이 없는데, "두 개의 2, 한 개의 2"인 수는 222인데 이 수의 다음 항은 2212가 아니라 32여야 하기 때문이다.

어떤 항이 주어졌을 때, 위 규칙을 따르면서 이 항이 존재하는 수열의 첫 번째 항을 찾아내는 프로그램을 작성하시오. 첫 번째 항은 절대 이전 항이 존재하지 않는다. 예를 들어 문제가 2221이면 답은 221이고, 문제가 312211이면 답은 1이다. 22처럼 이전 항이 자신과 동일할 경우는 예외로 그 자신이 첫 번째 항이 될 수 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄에 걸쳐 최대 100글자의 정수 n이 주어지며, 입력의 끝은 0으로 주어진다.

출력

각 n마다 첫 번째 항을 줄마다 양식에 맞춰서 출력한다.

예제 입력 1

2221
312211
22
0

예제 출력 1

Test 1: 221
Test 2: 1
Test 3: 22
W3sicHJvYmxlbV9pZCI6IjkyMTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjYWJcdWJjODhcdWM5ZjggXHVkNTZkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZTRcdWM3NGMgXHVjMjFjXHVjNWY0XHVjNWQwXHVjMTFjIFx1Yzc3NFx1YzViNFx1YzljMFx1YjI5NCBcdWQ1NmRcdWM3NDAgXHViYjM0XHVjNWM3XHVjNzdjXHVhZTRjPzxcL3A+XHJcblxyXG48cD4xLCAxMSwgMjEsIDEyMTEsIDExMTIyMSwgLi4uPFwvcD5cclxuXHJcbjxwPlx1YWRkY1x1Y2U1OVx1Yzc0MCBcdWM3NzRcdWI3ZWNcdWQ1NThcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWQ1NmRcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YjU0YyBcdWIyZTRcdWM3NGMgXHVkNTZkXHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVkNjA0XHVjN2FjIFx1ZDU2ZFx1Yzc0NCBcdWFjMTlcdWM3NDAgXHVjMjJiXHVjNzkwXHViNGU0XHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWNhYmNcdWFjMjAgXHVkNmM0LCBcdWFjMDEgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YmMxOFx1YmNmNVx1YjQxOFx1YjI5NCBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjNTVlXHVjNWQwIFx1YmQ5OVx1Yzc3NFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgMjFcdWM3NDAgJnF1b3Q7XHVkNTVjIFx1YWMxY1x1Yzc1OCAyLCBcdWQ1NWMgXHVhYzFjXHVjNzU4IDEmcXVvdDtcdWM3NzRcdWJiYzBcdWI4NWMgXHViMmU0XHVjNzRjIFx1ZDU2ZFx1Yzc0MCAxMjExXHVjNzc0IFx1YjQxY1x1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFkZGNcdWNlNTlcdWM1ZDAgXHViNTMwXHViNzdjXHVjMTFjIDExMTIyMSBcdWI0YTRcdWM1ZDBcdWIyOTQgMzEyMjExXHVjNzc0IFx1YzYyNFx1YWM4YyBcdWI0MWNcdWIyZTQoXHVjMTM4IFx1YWMxY1x1Yzc1OCAxLCBcdWI0NTAgXHVhYzFjXHVjNzU4IDIsIFx1ZDU1YyBcdWFjMWNcdWM3NTggMSkuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWQ1NmRcdWJmZDAgXHVjNTQ0XHViMmM4XHViNzdjIFx1Yzc3NFx1YzgwNCBcdWQ1NmRcdWIzYzQgXHVjNTRjXHVjNTQ0XHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIDIyMjFcdWM3NDAgXHVhZGY4IFx1Yzc5MFx1Y2NiNFx1Yjg1YyAmcXVvdDtcdWI0NTAgXHVhYzFjXHVjNzU4IDIsIFx1YjQ1MCBcdWFjMWNcdWM3NTggMSZxdW90O1x1Yzc3NCBcdWM3ODhcdWM1YzhcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViYmMwXHViODVjIFx1Yzc3NFx1YzgwNCBcdWQ1NmRcdWM3NDAgMjIxMVx1Yzc3NFx1YjJlNC4gXHViNjEwXHVkNTVjIDIyMTFcdWM3NTggXHVjNzc0XHVjODA0IFx1ZDU2ZFx1YjNjNCAyMjFcdWM3ODRcdWM3NDQgXHVjNTRjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjdmMFx1YjM3MCAyMjFcdWM3NTggXHVjNzc0XHVjODA0IFx1ZDU2ZFx1Yzc0MCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM2NWNcdWIwZDBcdWJhNzQgXHVjNzc0IFx1YWMxMlx1Yzc0NCBcdWM4MTVcdWJjZjRcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMjE4XHVhYzAwIFx1YzVjNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuIFx1YjYxMFx1ZDU1YyAyMjEyXHViM2M0IFx1Yzc3NFx1YzgwNCBcdWQ1NmRcdWM3NzQgXHVjNWM2XHViMjk0XHViMzcwLCAmcXVvdDtcdWI0NTAgXHVhYzFjXHVjNzU4IDIsIFx1ZDU1YyBcdWFjMWNcdWM3NTggMiZxdW90O1x1Yzc3OCBcdWMyMThcdWIyOTQgMjIyXHVjNzc4XHViMzcwIFx1Yzc3NCBcdWMyMThcdWM3NTggXHViMmU0XHVjNzRjIFx1ZDU2ZFx1Yzc0MCAyMjEyXHVhYzAwIFx1YzU0NFx1YjJjOFx1Yjc3YyAzMlx1YzVlY1x1YzU3YyBcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWI1YTQgXHVkNTZkXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzcwNCBcdWFkZGNcdWNlNTlcdWM3NDQgXHViNTMwXHViOTc0XHViYTc0XHVjMTFjIFx1Yzc3NCBcdWQ1NmRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDU2ZFx1Yzc0NCBcdWNjM2VcdWM1NDRcdWIwYjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWQ1NmRcdWM3NDAgXHVjODA4XHViMzAwIFx1Yzc3NFx1YzgwNCBcdWQ1NmRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWJiMzhcdWM4MWNcdWFjMDAgMjIyMVx1Yzc3NFx1YmE3NCBcdWIyZjVcdWM3NDAgMjIxXHVjNzc0XHVhY2UwLCBcdWJiMzhcdWM4MWNcdWFjMDAgMzEyMjExXHVjNzc0XHViYTc0IFx1YjJmNVx1Yzc0MCAxXHVjNzc0XHViMmU0LiAyMlx1Y2M5OFx1YjdmYyBcdWM3NzRcdWM4MDQgXHVkNTZkXHVjNzc0IFx1Yzc5MFx1YzJlMFx1YWNmYyBcdWIzZDlcdWM3N2NcdWQ1NjAgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzYwOFx1YzY3OFx1Yjg1YyBcdWFkZjggXHVjNzkwXHVjMmUwXHVjNzc0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkNTZkXHVjNzc0IFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWNkNWNcdWIzMDAgMTAwXHVhZTAwXHVjNzkwXHVjNzU4IFx1YzgxNVx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNzg1XHViODI1XHVjNzU4IFx1YjA1ZFx1Yzc0MCAwXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgblx1YjljOFx1YjJlNCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDU2ZFx1Yzc0NCBcdWM5MDRcdWI5YzhcdWIyZTQgXHVjNTkxXHVjMmRkXHVjNWQwIFx1YjlkZVx1Y2RiMFx1YzExYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTIxNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlByaW1vcmRpYWwgVmFsdWVzIiwiZGVzY3JpcHRpb24iOiI8cD5XaGF0JiMzOTtzIHRoZSBuZXh0IG51bWJlciBpbiB0aGUgZm9sbG93aW5nIHNlcXVlbmNlPzxcL3A+XHJcblxyXG48cD4xLCAxMSwgMjEsIDEyMTEsIDExMTIyMSwgLi4uPFwvcD5cclxuXHJcbjxwPk1vc3QgcGVvcGxlIGFzc3VtZSB0aGF0IHRoZSBzZXF1ZW5jZSBoYXMgc29tZXRoaW5nIHRvIGRvIHdpdGggbnVtZXJpYyB2YWx1ZXMgYW5kIHN0cnVnZ2xlIHRvIGZpbmQgYSBwYXR0ZXJuIC4gSW4gZmFjdCwgdGhlIHJ1bGUgZm9yIGdlbmVyYXRpbmcgdGhlIG5leHQgdmFsdWUgaW4gdGhlIHNlcmllcyBpcyB0aGF0IGVhY2ggdmFsdWUgaXMgYSBkZXNjcmlwdGlvbiBvZiB0aGUgcHJldmlvdXMgdmFsdWUuIEZvciBleGFtcGxlLCAyMSBjYW4gYmUgZGVzY3JpYmVkIGFzICZxdW90O29uZSAyLCBvbmUgMSZxdW90OywgbGVhZGluZyB0byB0aGUgbmV4dCB2YWx1ZSBvZiAxMjExLiBCeSB0aGlzIHJ1bGUsIHRoZSBhbnN3ZXIgdG8gdGhlIHByb2JsZW0gYWJvdmUgaXMgMzEyMjExICgmcXVvdDt0aHJlZSAxLCB0d28gMiwgb25lIDEmcXVvdDspLjxcL3A+XHJcblxyXG48cD5UaGUgcHJvY2VzcyBjYW4gYWxzbyBiZSByZXZlcnNlZCB0byBkZXRlcm1pbmUgcHJldmlvdXMgdmFsdWVzIGluIHRoZSBzZXF1ZW5jZS4gRm9yIGV4YW1wbGUsIHRoZSB2YWx1ZSB0aGF0IGNvbWVzIGJlZm9yZSAyMjIxICh0d28gMiwgdHdvIDEpIHdvdWxkIGJlIDIyMTEsIGFuZCB0aGUgdmFsdWUgYmVmb3JlIHRoYXQgd291bGQgYmUgMjIxLiBIb3dldmVyLCBub3QgZXZlcnkgdmFsdWUgaGFzIGEgcHJldmlvdXMgdmFsdWUuIEZvciBleGFtcGxlLCAyMjEgaGFzIG5vIHByZXZpb3VzIHZhbHVlIGJlY2F1c2UgaXQgaXNuJiMzOTt0IGEgdmFsaWQgZGVzY3JpcHRpb24sIGFuZCAyMjEyIGhhcyBubyBwcmV2aW91cyB2YWx1ZSBiZWNhdXNlIHRoZSB2YWx1ZSBpdCBkZXNjcmliZXMgKDIyMikgd291bGQgaGF2ZSBhIG5leHQgdmFsdWUgb2YgMzIsIG5vdCAyMjEyLjxcL3A+XHJcblxyXG48cD5UaGUgJnF1b3Q7cHJpbW9yZGlhbCB2YWx1ZSZxdW90OyBvZiBzb21lIHZhbHVlIGlzIGRlZmluZWQgYXMgdGhlIHZhbHVlIHRoYXQgd291bGQgZ2VuZXJhdGUgYSBzZXF1ZW5jZSBjb250YWluaW5nIHRoZSBnaXZlbiB2YWx1ZSBidXQgdGhhdCBpdHNlbGYgaGFzIG5vIHByZXZpb3VzIHZhbHVlLiBGb3IgZXhhbXBsZSwgaWYgdGhlIHN0YXJ0aW5nIHZhbHVlIGlzIDIyMjEgdGhlIHByaW1vcmRpYWwgdmFsdWUgaXMgMjIxLCBhbmQgaWYgdGhlIHN0YXJ0aW5nIHZhbHVlIGlzIDMxMjIxMSB0aGUgcHJpbW9yZGlhbCB2YWx1ZSBpcyAxLiBBcyBhIHNwZWNpYWwgY2FzZSwgdGhlIHZhbHVlIDIyIChmb3Igd2hpY2ggdGhlIHByZXZpb3VzIHZhbHVlIHdvdWxkIGFsc28gYmUgMjIpIGlzIGNvbnNpZGVyZWQgcHJpbW9yZGlhbC48XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgcHJpbW9yZGlhbCB2YWx1ZXMgZm9yIGdpdmVuIHN0YXJ0aW5nIHZhbHVlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IHdpbGwgY29uc2lzdCBvZiBzcGVjaWZpY2F0aW9ucyBmb3IgYSBzZXJpZXMgb2YgdGVzdHMuIEluZm9ybWF0aW9uIGZvciBlYWNoIHRlc3QgaXMgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIGEgc3RyaW5nIG9mIGRpZ2l0cyBvZiBsZW5ndGggMSAmbHQ7PSBuICZsdDsgMTAwIHRoYXQgc3BlY2lmaWVzIHRoZSBsYXN0IHZhbHVlIGluIGEgc2VxdWVuY2UgZGVmaW5lZCBhcyBhYm92ZS4gQSBsaW5lIGNvbnRhaW5pbmcgdGhlIHZhbHVlIDAgdGVybWluYXRlcyB0aGUgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHNob3VsZCBjb25zaXN0IG9mIG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY29tcHJpc2luZyB0aGUgdGVzdCBudW1iZXIgKGZvcm1hdHRlZCBhcyBzaG93bikgZm9sbG93ZWQgYnkgYSBzaW5nbGUgc3BhY2UgYW5kIHRoZSBwcmltb3JkaWFsIHZhbHVlIG9mIHRoZSBpbnB1dCB2YWx1ZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=