시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB97372636.620%

문제

팩스는 Run-Length Encoding(RLE)라고 불리는 인코딩을 사용한다. RLE란 아주 단순한 데이터 압축으로 데이터를 데이터와 반복된 횟수로 저장하는 방식을 말한다. 이 방식은 상대적으로 단순한 그래픽 이미지(아이콘, 글, 선 긋기)와 같이 반복이 많은 데이터를 압축할 때 좋다. 그러나 사진과 같이 반복이 별로 없다면 별로 좋지 않고, 거의 파일 크기를 두배로 늘린다.

아주 간단한 RLE 알고리즘을 이용하여 데이터 뭉치를 해독하는 프로그램을 작성해야 한다.

run은 2바이트를 사용하여 인코딩된다. 첫 번째 바이트는 반복횟수(count)를 뜻하고, 두 번째 바이트는 반복될 문자(값,value)를 뜻한다.

count 바이트는 첫 번째 비트가 1이며, 남은 7개의 비트로 [반복될 횟수-3]을 저장한다. 그러므로 최대 130번의 반복까지 저장할 수 있다. (즉 3회이상 반복되어야 이런 형식으로 인코딩된다는 뜻이다.) 값을 저장하는 value 바이트는 첫 번째 비트가 0이며 남은 7개의 비트로 [값-1]형태로 저장하여 1부터 128까지의 값을 저장할 수 있다.

입력

첫째 줄은 데이터 세트 수 P(1 ≤ P ≤ 1000)가 입력으로 들어온다. 각각의 데이터 세트는 여러 줄로 구성되어 있는데, 첫째 줄은 문제 번호와 디코딩해야 할 바이트 수 B(1 ≤ B ≤ 5000)가 공백으로 구분되어 들어온다. 남은 줄은 디코드해야할 데이터로 구성되어 있다. 데이터는 한 줄에 각 80개의 16진법 숫자이며 (마지막 줄은 80개보다 적을 수 있다), 16진법 숫자 2개가 하나의 바이트를 나타낸다.

(16진법 수는 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F로 구성되어 있다)

출력

각각의 데이터 세트에 대해 여러 줄의 출력을 해야한다. 첫째 줄은 코딩한 바이트 수를 출력한다. 남은 줄은 디코딩한 데이터를 출력하는데, 한 줄에 80개의 16진수로 출력한다. (마지막 줄은 80개보다 적을 수 있다)

예제 입력 1

4
2
0007
4
00F481A5
32
850080FF016666825A0A717273747580080110111384550301020399807700CC
2
A568

예제 출력 1

1
07
5
F4A5A5A5A5
44
0000000000000000FFFFFF66665A5A5A5A5A71727374758008011011135555555555555501020399
777777CC
40
68686868686868686868686868686868686868686868686868686868686868686868686868686868
W3sicHJvYmxlbV9pZCI6IjI2ODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMjlcdWMyYTQgXHViYzFiXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWQzMjlcdWMyYTRcdWIyOTQgUnVuLUxlbmd0aCBFbmNvZGluZyhSTEUpXHViNzdjXHVhY2UwIFx1YmQ4OFx1YjlhY1x1YjI5NCBcdWM3NzhcdWNmNTRcdWI1MjlcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiBSTEVcdWI3ODAgXHVjNTQ0XHVjOGZjIFx1YjJlOFx1YzIxY1x1ZDU1YyBcdWIzNzBcdWM3NzRcdWQxMzAgXHVjNTU1XHVjZDk1XHVjNzNjXHViODVjIFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yjk3YyBcdWIzNzBcdWM3NzRcdWQxMzBcdWM2NDAgXHViYzE4XHViY2Y1XHViNDFjIFx1ZDY5Zlx1YzIxOFx1Yjg1YyBcdWM4MDBcdWM3YTVcdWQ1NThcdWIyOTQgXHViYzI5XHVjMmRkXHVjNzQ0IFx1YjlkMFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YmMyOVx1YzJkZFx1Yzc0MCBcdWMwYzFcdWIzMDBcdWM4MDFcdWM3M2NcdWI4NWMgXHViMmU4XHVjMjFjXHVkNTVjIFx1YWRmOFx1Yjc5OFx1ZDUzZCBcdWM3NzRcdWJiZjhcdWM5YzAoXHVjNTQ0XHVjNzc0XHVjZjU4LCBcdWFlMDAsIFx1YzEyMCBcdWFlMGJcdWFlMzApXHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWJjMThcdWJjZjVcdWM3NzQgXHViOWNlXHVjNzQwIFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yjk3YyBcdWM1NTVcdWNkOTVcdWQ1NjAgXHViNTRjIFx1Yzg4Ylx1YjJlNC4gXHVhZGY4XHViN2VjXHViMDk4IFx1YzBhY1x1YzljNFx1YWNmYyBcdWFjMTlcdWM3NzQgXHViYzE4XHViY2Y1XHVjNzc0IFx1YmNjNFx1Yjg1YyBcdWM1YzZcdWIyZTRcdWJhNzQgXHViY2M0XHViODVjIFx1Yzg4Ylx1YzljMCBcdWM1NGFcdWFjZTAsIFx1YWM3MFx1Yzc1OCBcdWQzMGNcdWM3N2MgXHVkMDZjXHVhZTMwXHViOTdjIFx1YjQ1MFx1YmMzMFx1Yjg1YyBcdWIyOThcdWI5YjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzU0NFx1YzhmYyBcdWFjMDRcdWIyZThcdWQ1NWMgUkxFIFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHViMzcwXHVjNzc0XHVkMTMwIFx1YmI0OVx1Y2U1OFx1Yjk3YyBcdWQ1NzRcdWIzYzVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0cnVuXHVjNzQwIDJcdWJjMTRcdWM3NzRcdWQyYjhcdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTU4XHVjNWVjIFx1Yzc3OFx1Y2Y1NFx1YjUyOVx1YjQxY1x1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWJjMTRcdWM3NzRcdWQyYjhcdWIyOTQgXHViYzE4XHViY2Y1XHVkNjlmXHVjMjE4KGNvdW50KVx1Yjk3YyBcdWI3M2JcdWQ1NThcdWFjZTAsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHViYzE0XHVjNzc0XHVkMmI4XHViMjk0IFx1YmMxOFx1YmNmNVx1YjQyMCBcdWJiMzhcdWM3OTAoXHVhYzEyLHZhbHVlKVx1Yjk3YyBcdWI3M2JcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdGNvdW50IFx1YmMxNFx1Yzc3NFx1ZDJiOFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YmU0NFx1ZDJiOFx1YWMwMCAxXHVjNzc0XHViYTcwLCBcdWIwYThcdWM3NDAgN1x1YWMxY1x1Yzc1OCBcdWJlNDRcdWQyYjhcdWI4NWMgW1x1YmMxOFx1YmNmNVx1YjQyMCBcdWQ2OWZcdWMyMTgtM11cdWM3NDQgXHVjODAwXHVjN2E1XHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZWNcdWJiYzBcdWI4NWMgXHVjZDVjXHViMzAwIDEzMFx1YmM4OFx1Yzc1OCBcdWJjMThcdWJjZjVcdWFlNGNcdWM5YzAgXHVjODAwXHVjN2E1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWM5ODkgM1x1ZDY4Y1x1Yzc3NFx1YzBjMSBcdWJjMThcdWJjZjVcdWI0MThcdWM1YjRcdWM1N2MgXHVjNzc0XHViN2YwIFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM3NzhcdWNmNTRcdWI1MjlcdWI0MWNcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LikgXHVhYzEyXHVjNzQ0IFx1YzgwMFx1YzdhNVx1ZDU1OFx1YjI5NCB2YWx1ZSBcdWJjMTRcdWM3NzRcdWQyYjhcdWIyOTQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWJlNDRcdWQyYjhcdWFjMDAgMFx1Yzc3NFx1YmE3MCBcdWIwYThcdWM3NDAgN1x1YWMxY1x1Yzc1OCBcdWJlNDRcdWQyYjhcdWI4NWMgW1x1YWMxMi0xXVx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWM4MDBcdWM3YTVcdWQ1NThcdWM1ZWMgMVx1YmQ4MFx1ZDEzMCAxMjhcdWFlNGNcdWM5YzBcdWM3NTggXHVhYzEyXHVjNzQ0IFx1YzgwMFx1YzdhNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNzQwIFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMxMzhcdWQyYjggXHVjMjE4IFAoMSAmbGU7IFAgJmxlOyAxMDAwKVx1YWMwMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOFx1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVjOTA0XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM3NDAgXHViYjM4XHVjODFjIFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWI1MTRcdWNmNTRcdWI1MjlcdWQ1NzRcdWM1N2MgXHVkNTYwIFx1YmMxNFx1Yzc3NFx1ZDJiOCBcdWMyMTggQigxICZsZTsgQiAmbGU7IDUwMDApXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LiBcdWIwYThcdWM3NDAgXHVjOTA0XHVjNzQwIFx1YjUxNFx1Y2Y1NFx1YjRkY1x1ZDU3NFx1YzU3Y1x1ZDU2MCBcdWIzNzBcdWM3NzRcdWQxMzBcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHViMzcwXHVjNzc0XHVkMTMwXHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVhYzAxIDgwXHVhYzFjXHVjNzU4IDE2XHVjOWM0XHViYzk1IFx1YzIyYlx1Yzc5MFx1Yzc3NFx1YmE3MCAoXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1Yzc0MCA4MFx1YWMxY1x1YmNmNFx1YjJlNCBcdWM4MDFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNCksIDE2XHVjOWM0XHViYzk1IFx1YzIyYlx1Yzc5MCAyXHVhYzFjXHVhYzAwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJjMTRcdWM3NzRcdWQyYjhcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQoMTZcdWM5YzRcdWJjOTUgXHVjMjE4XHViMjk0IDAsMSwyLDMsNCw1LDYsNyw4LDksQSxCLEMsRCxFLEZcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDFcdWFjMDFcdWM3NTggXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjNWVjXHViN2VjIFx1YzkwNFx1Yzc1OCBcdWNkOWNcdWI4MjVcdWM3NDQgXHVkNTc0XHVjNTdjXHVkNTVjXHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNzQwIFx1Y2Y1NFx1YjUyOVx1ZDU1YyBcdWJjMTRcdWM3NzRcdWQyYjggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMGE4XHVjNzQwIFx1YzkwNFx1Yzc0MCBcdWI1MTRcdWNmNTRcdWI1MjlcdWQ1NWMgXHViMzcwXHVjNzc0XHVkMTMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NFx1YjM3MCwgXHVkNTVjIFx1YzkwNFx1YzVkMCA4MFx1YWMxY1x1Yzc1OCAxNlx1YzljNFx1YzIxOFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIChcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNzQwIDgwXHVhYzFjXHViY2Y0XHViMmU0IFx1YzgwMVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0KTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI2ODciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTaG93IE1lIFRoZSBGYXgiLCJkZXNjcmlwdGlvbiI6IjxwPkZheCBtYWNoaW5lcyB1c2UgYSBmb3JtIG9mIGNvbXByZXNzaW9uIGJhc2VkIG9uIHJ1bi1sZW5ndGggZW5jb2RpbmcuIFJ1bi1sZW5ndGggZW5jb2RpbmcgKFJMRSkgaXMgYSB2ZXJ5IHNpbXBsZSBmb3JtIG9mIGRhdGEgY29tcHJlc3Npb24gaW4gd2hpY2ggcnVucyBvZiBkYXRhICh0aGF0IGlzLCBzZXF1ZW5jZXMgaW4gd2hpY2ggdGhlIHNhbWUgZGF0YSB2YWx1ZSBvY2N1cnMgaW4gbWFueSBjb25zZWN1dGl2ZSBkYXRhIGVsZW1lbnRzKSBhcmUgc3RvcmVkIGFzIGEgc2luZ2xlIGRhdGEgdmFsdWUgYW5kIGNvdW50LCByYXRoZXIgdGhhbiBhcyB0aGUgb3JpZ2luYWwgcnVuLiBUaGlzIGlzIG1vc3QgdXNlZnVsIG9uIGRhdGEgdGhhdCBjb250YWlucyBtYW55IHN1Y2ggcnVuczogZm9yIGV4YW1wbGUsIHJlbGF0aXZlbHkgc2ltcGxlIGdyYXBoaWMgaW1hZ2VzIHN1Y2ggYXMgaWNvbnMsIHRleHQsIGFuZCBsaW5lIGRyYXdpbmdzLiBJdCBpcyBub3QgdXNlZnVsIHdpdGggZmlsZXMgdGhhdCBkb24mIzM5O3QgaGF2ZSBtYW55IHJ1bnMgYXMgaXQgY291bGQgcG90ZW50aWFsbHkgZG91YmxlIHRoZSBmaWxlIHNpemUgKHBob3RvZ3JhcGgsIGZvciBleGFtcGxlKS48XC9wPlxyXG5cclxuPHA+Rm9yIHRoaXMgcHJvYmxlbSwgeW91IHdpbGwgd3JpdGUgYSBwcm9ncmFtIHRoYXQgZGVjb2RlcyBhIGJsb2NrIG9mIGRhdGEgdXNpbmcgYSB2ZXJ5IHNpbXBsZSBSTEUgYWxnb3JpdGhtLiBBIHJ1biBpcyBlbmNvZGVkIHVzaW5nIGEgdHdvIGJ5dGUgc2VxdWVuY2UuIFRoZSBmaXJzdCBieXRlIG9mIHRoZSBzZXF1ZW5jZSBjb250YWlucyB0aGUgY291bnQsIGFuZCB0aGUgc2Vjb25kIGNvbnRhaW5zIHRoZSB2YWx1ZSB0byByZXBlYXQuIFRoZSBjb3VudCBpcyBlbmNvZGVkIHVzaW5nIGFuIDggYml0IHZhbHVlIHdpdGggdGhlIGhpZ2ggb3JkZXIgYml0IHNldCB0byAxLiBUaGUgcmVtYWluaW5nIDcgYml0cyByZXByZXNlbnQgdGhlIGNvdW50LTMuIFRoaXMgZ2l2ZXMgYSBtYXhpbXVtIHJ1biBjb3VudCBvZiAxMzAgcGVyIDIgYnl0ZSBzZXF1ZW5jZS4gKFRoaXMgaW1wbGllcyB0aGF0IHRoZSBtaW5pbXVtIHJ1biBjb3VudCBpcyAzKS4gQnl0ZXMgdGhhdCBhcmUgbm90IHBhcnQgb2YgYSBydW4gYXJlIGVuY29kZWQgYXMtaXMgd2l0aCBhIHByZWZpeCBieXRlIGluZGljYXRpbmcgdGhlIGNvdW50IG9mIGJ5dGVzIGluIHRoZSBub24tcnVuIG1pbnVzIDEsIDAgdGhyb3VnaCAxMjcsIHJlcHJlc2VudGluZyBhIHJhbmdlIG9mIDEgLSAxMjggKHRoZSBoaWdoIG9yZGVyIGJpdCB3aWxsIGFsd2F5cyBiZSAwIGluIHRoZSBjYXNlIG9mIG5vbnJ1biBkYXRhKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKDEgJmxlOyBQICZsZTsgMTAwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzIHRoYXQgZm9sbG93LiBFYWNoIGRhdGEgc2V0IGNvbnNpc3RzIG9mIG11bHRpcGxlIGxpbmVzLiBUaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gKDIpIGRlY2ltYWwgaW50ZWdlciB2YWx1ZXM6IHRoZSBwcm9ibGVtIG51bWJlciwgZm9sbG93ZWQgYnkgYSBzcGFjZSwgZm9sbG93ZWQgYnkgdGhlIG51bWJlciBvZiBieXRlcyBCLCAoMSAmbGU7IEIgJmxlOyA1MDAwKSwgdG8gZGVjb2RlLiBUaGUgcmVtYWluaW5nIGxpbmUocykgY29udGFpbihzKSB0aGUgZGF0YSB0byBiZSBkZWNvZGVkLiBFYWNoIGxpbmUgb2YgZGF0YSB0byBkZWNvZGUgY29udGFpbnMgODAgaGV4YWRlY2ltYWwgZGlnaXRzIChleGNlcHQgdGhlIGxhc3QgbGluZSwgd2hpY2ggbWF5IGNvbnRhaW4gbGVzcykuIDIgaGV4YWRlY2ltYWwgZGlnaXRzIGFyZSB1c2VkIHRvIHJlcHJlc2VudCBlYWNoIGJ5dGUuIEhleGFkZWNpbWFsIGRpZ2l0cyBhcmU6IDAsMSwyLDMsNCw1LDYsNyw4LDksQSxCLEMsRCxFLEY8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCwgdGhlcmUgYXJlIG11bHRpcGxlIGxpbmVzIG9mIG91dHB1dC4gVGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYSBkZWNpbWFsIGludGVnZXIgZ2l2aW5nIHRoZSBkYXRhIHNldCBudW1iZXIgZm9sbG93ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIGZvbGxvd2VkIGJ5IGEgZGVjaW1hbCBpbnRlZ2VyIGdpdmluZyB0aGUgdG90YWwgbnVtYmVyIG9mIGRlY29kZWQgYnl0ZXMuIFRoZSByZW1haW5pbmcgbGluZXMgY29udGFpbiB0aGUgZGVjb2RlZCBkYXRhLCA4MCBoZXhhZGVjaW1hbCBkaWdpdHMgcGVyIGxpbmUsIGV4Y2VwdCB0aGUgbGFzdCBsaW5lIHdoaWNoIG1heSBjb250YWluIGxlc3MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==