3197 - 인코딩

• Submit
• Status
• Discuss
• Summary

Description

지아희조와 이노인호는 서로 사랑하는 사이이다. 하지만 사회의 눈초리는 그들의 관계를 인정해주지 않았고, 때문에 둘은 비밀연애를 하게 되었다.

지아희조와 이노인호는 서로의 대화내용이 들키지 않게 만들기 위해, 둘만의 비밀암호를 하나 만들었다.

 

그들은 먼저 행렬의 세로(R)와 가로(C)를 비밀스럽게 정했다. 보내는 사람은 다음과 같은 법칙을 이용하여 문자열의 중간형태를 인코딩한다.

문자는 대문자와 『　　』(공백) 으로 이루어진다. 각 문자들은 아래와 같은 10진수로 대응된다.

 

『　　』 = 0, A = 1, B = 2, C = 3, ... , Y = 25, Z = 26

보내는 사람은 보내려는 문자의 10진수 값을 5자리 이진수로 변환하여 행렬을 만든다. 행렬을 만드는 순서는 아래의 그림에서 표시된 순서를 따른다.

 

 

0		0		0		0
						↓
1		1		0		1
↑				↓		↓
0		0		1		0
↑						↓
1		1		0		0

 

 

A = 00001, C = 00011, M = 01101

(one extra 0)

위의 예시는 R=4, C=4 일 때 ACM 이라는 문자열을 행렬로 만들었을 때의 모습이다. 남는 공간에는 0을 채운다.

 

이렇게 만들어진 행렬에서 제일 위쪽 행부터 시작해서 행들의 값을 한줄로 합쳐서 상대편에게 보낸다. 위의 예시에서는 0000110100101100 으로 인코딩 된다.

 

 

오늘은 지아희조가 사랑의 메세지를 보내는 날이다. 그러나 최근 블X보드 사이트가 터지는 일이 발생하여 바빠지게 된 지아희조는 비밀 메세지를 대신 만들어주는 프로그램을 당신에게 부탁했다.

그의 열정과 사랑에 감동한 당신은 이제 이 프로그램을 만들어주어야한다. 화이팅!

 

Input

첫 줄에는 테스트케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다.

각 테스트케이스마다 R C, 그리고 보내려는 문자열 P가 한줄에 걸쳐 주어진다. (1≤R,C≤20, |P| ≤ (R*C)/5)

Output

각각 테스트케이스마다 한줄에 하나씩 다음의 형식에 맞춰서 출력한다.

i C

i는 테스트케이스의 번호이고, C는 P를 인코딩시킨 결과물이다.

Sample Input

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

Sample Output

1 0000110100101100
2 0110000010
3 010000001001
4 0100001000011010110000010

Source

Regionals 2007, North America - Greater NY