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

문제

규현이는 승환이에게 사랑을 담은 문자 메시지를 자주 보낸다. 이것을 남에게 보이기 싫었던 규현이는 승환이와 비밀 규칙을 만들었다.

규현이는 비밀 메시지를 만들기 위한 행렬의 행의 수 R과 열의 수 C를 정했다. 그 다음 다음과 같은 규칙으로 비밀 메시지를 만든다.

  1. 모든 글자는 알파벳 대문자와 공백으로 이루어져 있다.
  2. 글자는 다음과 같이 숫자로 바뀐다. 공백 = 0, A = 1, B = 2, ..., Y = 25, Z = 26

먼저 규현이는 문자를 위 규칙을 이용해 글자를 숫자로 바꾼 다음에 이것은 5자리 이진수로 바꾼다. 그 다음 아래 그림과 같이 소용돌이 패턴으로 행렬에 채운다. 행렬의 모든 칸을 채우지 못할 때는, 0으로 계속 채운다. 예를 들어 규현이가 보내려는 메시지가 "ACM"이고, R=4, C=4로 정했다면, 다음과 같이 행렬을 채우면 된다.

A = 00001, C = 00011, M = 01101, 모자라는 칸은 0으로 채운다.

그 다음 행렬을 행 우선으로 읽은 뒤 (Row Major Order)에 승환이에게 보낸다.

위의 예시를 메시지로 보낸다면 0000110100101100이 된다.

R, C, 규현이가 보내려고 하는 메시지가 주어졌을 때, 이를 승환이에게 보내는 비밀 메시지로 변환하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 1,000) 각 테스트 케이스는 한 줄로 이루어져 있고, R, 공백, C, 공백, 규현이가 보내려고 하는 메시지로 이루어져 있다. (1 ≤ R,C ≤ 21) 메시지는 [A-Z]와 공백으로만 이루어져 있고, 이 길이는 항상 (R*C)/5보다 작거나 같다.

출력

각 테스트 케이스에 대해 규현이가 문자로 보낼 비밀 메시지를 출력한다.

예제 입력 1

4
4 4 ACM
5 2 HI
2 6 HI
5 5 HI HO

예제 출력 1

0000110100101100
0110000010
010000001001
0100001000011010110000010
W3sicHJvYmxlbV9pZCI6IjI3MTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkZGNcdWQ2MDRcdWM3NzRcdWM3NTggXHVjMGFjXHViNzkxXHVjNzQ0IFx1YjJmNFx1Yzc0MCBcdWJiMzhcdWM3OTBcdWJhNTRcdWMyZGNcdWM5YzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWRkY1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWMyYjlcdWQ2NThcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjMGFjXHViNzkxXHVjNzQ0IFx1YjJmNFx1Yzc0MCBcdWJiMzhcdWM3OTAgXHViYTU0XHVjMmRjXHVjOWMwXHViOTdjIFx1Yzc5MFx1YzhmYyBcdWJjZjRcdWIwYjhcdWIyZTQuIFx1Yzc3NFx1YWM4M1x1Yzc0NCBcdWIwYThcdWM1ZDBcdWFjOGMgXHViY2Y0XHVjNzc0XHVhZTMwIFx1YzJlYlx1YzVjOFx1YjM1OCBcdWFkZGNcdWQ2MDRcdWM3NzRcdWIyOTQgXHVjMmI5XHVkNjU4XHVjNzc0XHVjNjQwIFx1YmU0NFx1YmMwMCBcdWFkZGNcdWNlNTlcdWM3NDQgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZGNcdWQ2MDRcdWM3NzRcdWIyOTQgXHViZTQ0XHViYzAwIFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTVjIFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWQ1ODlcdWM3NTggXHVjMjE4IFJcdWFjZmMgXHVjNWY0XHVjNzU4IFx1YzIxOCBDXHViOTdjIFx1YzgxNVx1ZDU4OFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWRkY1x1Y2U1OVx1YzczY1x1Yjg1YyBcdWJlNDRcdWJjMDAgXHViYTU0XHVjMmRjXHVjOWMwXHViOTdjIFx1YjljY1x1YjRlMFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgXHVhZTAwXHVjNzkwXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWM2NDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWUwMFx1Yzc5MFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWJjMTRcdWIwMTBcdWIyZTQuIFx1YWNmNVx1YmMzMSA9IDAsIEEgPSAxLCBCID0gMiwgLi4uLCBZID0gMjUsIFogPSAyNjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YmEzY1x1YzgwMCBcdWFkZGNcdWQ2MDRcdWM3NzRcdWIyOTQgXHViYjM4XHVjNzkwXHViOTdjIFx1YzcwNCBcdWFkZGNcdWNlNTlcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0IFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWMyMmJcdWM3OTBcdWI4NWMgXHViYzE0XHVhZmJjIFx1YjJlNFx1Yzc0Y1x1YzVkMCBcdWM3NzRcdWFjODNcdWM3NDAgNVx1Yzc5MFx1YjlhYyBcdWM3NzRcdWM5YzRcdWMyMThcdWI4NWMgXHViYzE0XHVhZmJjXHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzE4Y1x1YzZhOVx1YjNjY1x1Yzc3NCBcdWQzMjhcdWQxMzRcdWM3M2NcdWI4NWMgXHVkNTg5XHViODJjXHVjNWQwIFx1Y2M0NFx1YzZiNFx1YjJlNC4gXHVkNTg5XHViODJjXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWNlNzhcdWM3NDQgXHVjYzQ0XHVjNmIwXHVjOWMwIFx1YmFiYlx1ZDU2MCBcdWI1NGNcdWIyOTQsIDBcdWM3M2NcdWI4NWMgXHVhY2M0XHVjMThkIFx1Y2M0NFx1YzZiNFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWFkZGNcdWQ2MDRcdWM3NzRcdWFjMDAgXHViY2Y0XHViMGI0XHViODI0XHViMjk0IFx1YmE1NFx1YzJkY1x1YzljMFx1YWMwMCAmcXVvdDtBQ00mcXVvdDtcdWM3NzRcdWFjZTAsIFI9NCwgQz00XHViODVjIFx1YzgxNVx1ZDU4OFx1YjJlNFx1YmE3NCwgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWQ1ODlcdWI4MmNcdWM3NDQgXHVjYzQ0XHVjNmIwXHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9TY3JlZW4lMjBTaG90JTIwMjAxMi0xMC0wNiUyMGF0JTIwJUVDJTk4JUE0JUVDJUEwJTg0JTIwMTJfMzZfMzUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTg1cHg7IHdpZHRoOjEyNnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkEgPSAwMDAwMSwgQyA9IDAwMDExLCBNID0gMDExMDEsIFx1YmFhOFx1Yzc5MFx1Yjc3Y1x1YjI5NCBcdWNlNzhcdWM3NDAgMFx1YzczY1x1Yjg1YyBcdWNjNDRcdWM2YjRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWIyZTRcdWM3NGMgXHVkNTg5XHViODJjXHVjNzQ0IFx1ZDU4OSBcdWM2YjBcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNzdkXHVjNzQwIFx1YjRhNCAoUm93IE1ham9yIE9yZGVyKVx1YzVkMCBcdWMyYjlcdWQ2NThcdWM3NzRcdWM1ZDBcdWFjOGMgXHViY2Y0XHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVjNjA4XHVjMmRjXHViOTdjIFx1YmE1NFx1YzJkY1x1YzljMFx1Yjg1YyBcdWJjZjRcdWIwYjhcdWIyZTRcdWJhNzQgMDAwMDExMDEwMDEwMTEwMFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlIsIEMsIFx1YWRkY1x1ZDYwNFx1Yzc3NFx1YWMwMCBcdWJjZjRcdWIwYjRcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YmE1NFx1YzJkY1x1YzljMFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzRcdWI5N2MgXHVjMmI5XHVkNjU4XHVjNzc0XHVjNWQwXHVhYzhjIFx1YmNmNFx1YjBiNFx1YjI5NCBcdWJlNDRcdWJjMDAgXHViYTU0XHVjMmRjXHVjOWMwXHViODVjIFx1YmNjMFx1ZDY1OFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBUICZsZTsgMSwwMDApIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgUiwgXHVhY2Y1XHViYzMxLCBDLCBcdWFjZjVcdWJjMzEsIFx1YWRkY1x1ZDYwNFx1Yzc3NFx1YWMwMCBcdWJjZjRcdWIwYjRcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YmE1NFx1YzJkY1x1YzljMFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoMSAmbGU7IFIsQyAmbGU7IDIxKSBcdWJhNTRcdWMyZGNcdWM5YzBcdWIyOTQgW0EtWl1cdWM2NDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1Yzc3NCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVkNTZkXHVjMGMxIChSKkMpXC81XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YWRkY1x1ZDYwNFx1Yzc3NFx1YWMwMCBcdWJiMzhcdWM3OTBcdWI4NWMgXHViY2Y0XHViMGJjIFx1YmU0NFx1YmMwMCBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI3MTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFbmNvZGluZyIsImRlc2NyaXB0aW9uIjoiPHA+Q2hpcCBhbmQgRGFsZSBoYXZlIGRldmlzZWQgYW4gZW5jcnlwdGlvbiBtZXRob2QgdG8gaGlkZSB0aGVpciAod3JpdHRlbikgdGV4dCBtZXNzYWdlcy4gVGhleSBmaXJzdCBhZ3JlZSBzZWNyZXRseSBvbiB0d28gbnVtYmVycyB0aGF0IHdpbGwgYmUgdXNlZCBhcyB0aGUgbnVtYmVyIG9mIHJvd3MgKFIpIGFuZCBjb2x1bW5zIChDKSBpbiBhIG1hdHJpeC4gVGhlIHNlbmRlciBlbmNvZGVzIGFuIGludGVybWVkaWF0ZSBmb3JtYXQgdXNpbmcgdGhlIGZvbGxvd2luZyBydWxlczombmJzcDs8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5UaGUgdGV4dCBpcyBmb3JtZWQgd2l0aCB1cHBlcmNhc2UgbGV0dGVycyBbQS1aXSBhbmQgJmx0O3NwYWNlJmd0Oy48XC9saT5cclxuXHQ8bGk+RWFjaCB0ZXh0IGNoYXJhY3RlciB3aWxsIGJlIHJlcHJlc2VudGVkIGJ5IGRlY2ltYWwgdmFsdWVzIGFzIGZvbGxvd3M6Jm5ic3A7PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+Jmx0O3NwYWNlJmd0OyA9IDAsIEEgPSAxLCBCID0gMiwgQyA9IDMsIC4uLiwgWSA9IDI1LCBaID0gMjY8XC9wPlxyXG5cclxuPHA+VGhlIHNlbmRlciBlbnRlcnMgdGhlIDUgZGlnaXQgYmluYXJ5IHJlcHJlc2VudGF0aW9uIG9mIHRoZSBjaGFyYWN0ZXJzJnJzcXVvOyB2YWx1ZXMgaW4gYSBzcGlyYWwgcGF0dGVybiBhbG9uZyB0aGUgbWF0cml4IGFzIHNob3duIGJlbG93LiBUaGUgbWF0cml4IGlzIHBhZGRlZCBvdXQgd2l0aCB6ZXJvZXMgKDApIHRvIGZpbGwgdGhlIG1hdHJpeCBjb21wbGV0ZWx5LiBGb3IgZXhhbXBsZSwgaWYgdGhlIHRleHQgdG8gZW5jb2RlIGlzOiAmcXVvdDtBQ00mcXVvdDsgYW5kIFI9NCBhbmQgQz00LCB0aGUgbWF0cml4IHdvdWxkIGJlIGZpbGxlZCBpbiBhcyBmb2xsb3dzOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL1NjcmVlbiUyMFNob3QlMjAyMDEyLTEwLTA2JTIwYXQlMjAlRUMlOTglQTQlRUMlQTAlODQlMjAxMl8zNl8zNS5wbmdcIiBzdHlsZT1cImhlaWdodDoxODVweDsgd2lkdGg6MTI2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QSA9IDAwMDAxLCBDID0gMDAwMTEsIE0gPSAwMTEwMSAob25lIGV4dHJhIDApJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBiaXRzIGluIHRoZSBtYXRyaXggYXJlIHRoZW4gY29uY2F0ZW5hdGVkIHRvZ2V0aGVyIGluIHJvdyBtYWpvciBvcmRlciBhbmQgc2VudCB0byB0aGUgcmVjZWl2ZXIuIFRoZSBleGFtcGxlIGFib3ZlIHdvdWxkIGJlIGVuY29kZWQgYXM6IDAwMDAxMTAxMDAxMDExMDA8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgTiwgKDEgJmxlOyBOICZsZTsgMTAwMCkgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhc2V0cyB0aGF0IGZvbGxvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBkYXRhc2V0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgb2YgaW5wdXQgY29udGFpbmluZyBSICgxJmx0Oz1SJmx0Oz0yMCksIGEgc3BhY2UsIEMgKDEmbHQ7PUMmbHQ7PTIwKSwgYSBzcGFjZSwgYW5kIGEgdGV4dCBzdHJpbmcgY29uc2lzdGluZyBvZiB1cHBlcmNhc2UgbGV0dGVycyBbQS1aXSBhbmQgJmx0O3NwYWNlJmd0Oy4gVGhlIGxlbmd0aCBvZiB0aGUgdGV4dCBzdHJpbmcgaXMgZ3VhcmFudGVlZCB0byBiZSAmbHQ7PSAoUipDKVwvNS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhc2V0LCB5b3Ugc2hvdWxkIGdlbmVyYXRlIG9uZSBsaW5lIG9mIG91dHB1dCB3aXRoIHRoZSBmb2xsb3dpbmcgdmFsdWVzOiBUaGUgZGF0YXNldCBudW1iZXIgYXMgYSBkZWNpbWFsIGludGVnZXIgKHN0YXJ0IGNvdW50aW5nIGF0IG9uZSksIGEgc3BhY2UsIGFuZCBhIHN0cmluZyBvZiBiaW5hcnkgZGlnaXRzIChSKkMpIGxvbmcgZGVzY3JpYmluZyB0aGUgZW5jb2RlZCB0ZXh0LiBUaGUgYmluYXJ5IHN0cmluZyByZXByZXNlbnRzIHRoZSB2YWx1ZXMgdXNlZCB0byBmaWxsIGluIHRoZSBtYXRyaXggaW4gcm93bWFqb3Igb3JkZXIuIFlvdSBtYXkgaGF2ZSB0byBmaWxsIG91dCB0aGUgbWF0cml4IHdpdGggemVyb2VzICgwKSB0byBjb21wbGV0ZSB0aGUgbWF0cml4LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=