시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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
W3sicHJvYmxlbV9pZCI6IjkyMTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDU2ZCIsImRlc2NyaXB0aW9uIjoiPHA+XHViMmU0XHVjNzRjIFx1YzIxY1x1YzVmNFx1YzVkMFx1YzExYyBcdWM3NzRcdWM1YjRcdWM5YzBcdWIyOTQgXHVkNTZkXHVjNzQwIFx1YmIzNFx1YzVjN1x1Yzc3Y1x1YWU0Yz88XC9wPlxyXG5cclxuPHA+MSwgMTEsIDIxLCAxMjExLCAxMTEyMjEsIC4uLjxcL3A+XHJcblxyXG48cD5cdWFkZGNcdWNlNTlcdWM3NDAgXHVjNzc0XHViN2VjXHVkNTU4XHViMmU0LiBcdWM1YjRcdWI1YTQgXHVkNTZkXHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWI1NGMgXHViMmU0XHVjNzRjIFx1ZDU2ZFx1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1ZDYwNFx1YzdhYyBcdWQ1NmRcdWM3NDQgXHVhYzE5XHVjNzQwIFx1YzIyYlx1Yzc5MFx1YjRlNFx1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWIzYzRcdWI4NWQgXHVjYWJjXHVhYzIwIFx1ZDZjNCwgXHVhYzAxIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWJjMThcdWJjZjVcdWI0MThcdWIyOTQgXHVkNjlmXHVjMjE4XHViOTdjIFx1YzU1ZVx1YzVkMCBcdWJkOTlcdWM3NzRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IDIxXHVjNzQwICZxdW90O1x1ZDU1YyBcdWFjMWNcdWM3NTggMiwgXHVkNTVjIFx1YWMxY1x1Yzc1OCAxJnF1b3Q7XHVjNzc0XHViYmMwXHViODVjIFx1YjJlNFx1Yzc0YyBcdWQ1NmRcdWM3NDAgMTIxMVx1Yzc3NCBcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNWQwIFx1YjUzMFx1Yjc3Y1x1YzExYyAxMTEyMjEgXHViNGE0XHVjNWQwXHViMjk0IDMxMjIxMVx1Yzc3NCBcdWM2MjRcdWFjOGMgXHViNDFjXHViMmU0KFx1YzEzOCBcdWFjMWNcdWM3NTggMSwgXHViNDUwIFx1YWMxY1x1Yzc1OCAyLCBcdWQ1NWMgXHVhYzFjXHVjNzU4IDEpLjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVkNTZkXHViZmQwIFx1YzU0NFx1YjJjOFx1Yjc3YyBcdWM3NzRcdWM4MDQgXHVkNTZkXHViM2M0IFx1YzU0Y1x1YzU0NFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiAyMjIxXHVjNzQwIFx1YWRmOCBcdWM3OTBcdWNjYjRcdWI4NWMgJnF1b3Q7XHViNDUwIFx1YWMxY1x1Yzc1OCAyLCBcdWI0NTAgXHVhYzFjXHVjNzU4IDEmcXVvdDtcdWM3NzQgXHVjNzg4XHVjNWM4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YmJjMFx1Yjg1YyBcdWM3NzRcdWM4MDQgXHVkNTZkXHVjNzQwIDIyMTFcdWM3NzRcdWIyZTQuIFx1YjYxMFx1ZDU1YyAyMjExXHVjNzU4IFx1Yzc3NFx1YzgwNCBcdWQ1NmRcdWIzYzQgMjIxXHVjNzg0XHVjNzQ0IFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAgMjIxXHVjNzU4IFx1Yzc3NFx1YzgwNCBcdWQ1NmRcdWM3NDAgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNjVjXHViMGQwXHViYTc0IFx1Yzc3NCBcdWFjMTJcdWM3NDQgXHVjODE1XHViY2Y0XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzIxOFx1YWMwMCBcdWM1YzZcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWI2MTBcdWQ1NWMgMjIxMlx1YjNjNCBcdWM3NzRcdWM4MDQgXHVkNTZkXHVjNzc0IFx1YzVjNlx1YjI5NFx1YjM3MCwgJnF1b3Q7XHViNDUwIFx1YWMxY1x1Yzc1OCAyLCBcdWQ1NWMgXHVhYzFjXHVjNzU4IDImcXVvdDtcdWM3NzggXHVjMjE4XHViMjk0IDIyMlx1Yzc3OFx1YjM3MCBcdWM3NzQgXHVjMjE4XHVjNzU4IFx1YjJlNFx1Yzc0YyBcdWQ1NmRcdWM3NDAgMjIxMlx1YWMwMCBcdWM1NDRcdWIyYzhcdWI3N2MgMzJcdWM1ZWNcdWM1N2MgXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1ZDU2ZFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3MDQgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjUzMFx1Yjk3NFx1YmE3NFx1YzExYyBcdWM3NzQgXHVkNTZkXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWQ1NmRcdWM3NDQgXHVjYzNlXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkNTZkXHVjNzQwIFx1YzgwOFx1YjMwMCBcdWM3NzRcdWM4MDQgXHVkNTZkXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHViYjM4XHVjODFjXHVhYzAwIDIyMjFcdWM3NzRcdWJhNzQgXHViMmY1XHVjNzQwIDIyMVx1Yzc3NFx1YWNlMCwgXHViYjM4XHVjODFjXHVhYzAwIDMxMjIxMVx1Yzc3NFx1YmE3NCBcdWIyZjVcdWM3NDAgMVx1Yzc3NFx1YjJlNC4gMjJcdWNjOThcdWI3ZmMgXHVjNzc0XHVjODA0IFx1ZDU2ZFx1Yzc3NCBcdWM3OTBcdWMyZTBcdWFjZmMgXHViM2Q5XHVjNzdjXHVkNTYwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM2MDhcdWM2NzhcdWI4NWMgXHVhZGY4IFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDU2ZFx1Yzc3NCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjZDVjXHViMzAwIDEwMFx1YWUwMFx1Yzc5MFx1Yzc1OCBcdWM4MTVcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWIwNWRcdWM3NDAgMFx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIG5cdWI5YzhcdWIyZTQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWQ1NmRcdWM3NDQgXHVjOTA0XHViOWM4XHViMmU0IFx1YzU5MVx1YzJkZFx1YzVkMCBcdWI5ZGVcdWNkYjBcdWMxMWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkyMTQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQcmltb3JkaWFsIFZhbHVlcyIsImRlc2NyaXB0aW9uIjoiPHA+V2hhdCYjMzk7cyB0aGUgbmV4dCBudW1iZXIgaW4gdGhlIGZvbGxvd2luZyBzZXF1ZW5jZT88XC9wPlxyXG5cclxuPHA+MSwgMTEsIDIxLCAxMjExLCAxMTEyMjEsIC4uLjxcL3A+XHJcblxyXG48cD5Nb3N0IHBlb3BsZSBhc3N1bWUgdGhhdCB0aGUgc2VxdWVuY2UgaGFzIHNvbWV0aGluZyB0byBkbyB3aXRoIG51bWVyaWMgdmFsdWVzIGFuZCBzdHJ1Z2dsZSB0byBmaW5kIGEgcGF0dGVybiAuIEluIGZhY3QsIHRoZSBydWxlIGZvciBnZW5lcmF0aW5nIHRoZSBuZXh0IHZhbHVlIGluIHRoZSBzZXJpZXMgaXMgdGhhdCBlYWNoIHZhbHVlIGlzIGEgZGVzY3JpcHRpb24gb2YgdGhlIHByZXZpb3VzIHZhbHVlLiBGb3IgZXhhbXBsZSwgMjEgY2FuIGJlIGRlc2NyaWJlZCBhcyAmcXVvdDtvbmUgMiwgb25lIDEmcXVvdDssIGxlYWRpbmcgdG8gdGhlIG5leHQgdmFsdWUgb2YgMTIxMS4gQnkgdGhpcyBydWxlLCB0aGUgYW5zd2VyIHRvIHRoZSBwcm9ibGVtIGFib3ZlIGlzIDMxMjIxMSAoJnF1b3Q7dGhyZWUgMSwgdHdvIDIsIG9uZSAxJnF1b3Q7KS48XC9wPlxyXG5cclxuPHA+VGhlIHByb2Nlc3MgY2FuIGFsc28gYmUgcmV2ZXJzZWQgdG8gZGV0ZXJtaW5lIHByZXZpb3VzIHZhbHVlcyBpbiB0aGUgc2VxdWVuY2UuIEZvciBleGFtcGxlLCB0aGUgdmFsdWUgdGhhdCBjb21lcyBiZWZvcmUgMjIyMSAodHdvIDIsIHR3byAxKSB3b3VsZCBiZSAyMjExLCBhbmQgdGhlIHZhbHVlIGJlZm9yZSB0aGF0IHdvdWxkIGJlIDIyMS4gSG93ZXZlciwgbm90IGV2ZXJ5IHZhbHVlIGhhcyBhIHByZXZpb3VzIHZhbHVlLiBGb3IgZXhhbXBsZSwgMjIxIGhhcyBubyBwcmV2aW91cyB2YWx1ZSBiZWNhdXNlIGl0IGlzbiYjMzk7dCBhIHZhbGlkIGRlc2NyaXB0aW9uLCBhbmQgMjIxMiBoYXMgbm8gcHJldmlvdXMgdmFsdWUgYmVjYXVzZSB0aGUgdmFsdWUgaXQgZGVzY3JpYmVzICgyMjIpIHdvdWxkIGhhdmUgYSBuZXh0IHZhbHVlIG9mIDMyLCBub3QgMjIxMi48XC9wPlxyXG5cclxuPHA+VGhlICZxdW90O3ByaW1vcmRpYWwgdmFsdWUmcXVvdDsgb2Ygc29tZSB2YWx1ZSBpcyBkZWZpbmVkIGFzIHRoZSB2YWx1ZSB0aGF0IHdvdWxkIGdlbmVyYXRlIGEgc2VxdWVuY2UgY29udGFpbmluZyB0aGUgZ2l2ZW4gdmFsdWUgYnV0IHRoYXQgaXRzZWxmIGhhcyBubyBwcmV2aW91cyB2YWx1ZS4gRm9yIGV4YW1wbGUsIGlmIHRoZSBzdGFydGluZyB2YWx1ZSBpcyAyMjIxIHRoZSBwcmltb3JkaWFsIHZhbHVlIGlzIDIyMSwgYW5kIGlmIHRoZSBzdGFydGluZyB2YWx1ZSBpcyAzMTIyMTEgdGhlIHByaW1vcmRpYWwgdmFsdWUgaXMgMS4gQXMgYSBzcGVjaWFsIGNhc2UsIHRoZSB2YWx1ZSAyMiAoZm9yIHdoaWNoIHRoZSBwcmV2aW91cyB2YWx1ZSB3b3VsZCBhbHNvIGJlIDIyKSBpcyBjb25zaWRlcmVkIHByaW1vcmRpYWwuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIHByaW1vcmRpYWwgdmFsdWVzIGZvciBnaXZlbiBzdGFydGluZyB2YWx1ZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCB3aWxsIGNvbnNpc3Qgb2Ygc3BlY2lmaWNhdGlvbnMgZm9yIGEgc2VyaWVzIG9mIHRlc3RzLiBJbmZvcm1hdGlvbiBmb3IgZWFjaCB0ZXN0IGlzIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBhIHN0cmluZyBvZiBkaWdpdHMgb2YgbGVuZ3RoIDEgJmx0Oz0gbiAmbHQ7IDEwMCB0aGF0IHNwZWNpZmllcyB0aGUgbGFzdCB2YWx1ZSBpbiBhIHNlcXVlbmNlIGRlZmluZWQgYXMgYWJvdmUuIEEgbGluZSBjb250YWluaW5nIHRoZSB2YWx1ZSAwIHRlcm1pbmF0ZXMgdGhlIGlucHV0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBzaG91bGQgY29uc2lzdCBvZiBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNvbXByaXNpbmcgdGhlIHRlc3QgbnVtYmVyIChmb3JtYXR0ZWQgYXMgc2hvd24pIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlIGFuZCB0aGUgcHJpbW9yZGlhbCB2YWx1ZSBvZiB0aGUgaW5wdXQgdmFsdWUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d