팩스

팩스 기계는 run-length encoding(RLE)을 사용해 데이터를 압축한다. 데이터는 같은 바이트 값이 연속해서 나타나는 수열로 볼 수 있고, 이렇게 같은 값이 이어진 구간을 run이라고 한다. RLE는 수열을 그대로 저장하는 대신, 하나의 데이터 값과 그 값이 반복된 횟수로 run을 표현한다. 이 방식은 아이콘, 텍스트, 선 그림처럼 run이 많은 단순한 그래픽 데이터에 효과적이다. 반대로 사진처럼 run이 적은 데이터에는 원래보다 더 큰 결과가 나올 수도 있다.

한 블록의 데이터를 RLE 알고리즘으로 인코딩하려고 한다. 하나의 run은 2바이트로 표현한다. 첫 번째 바이트는 반복 횟수를 나타내고, 두 번째 바이트는 반복되는 값을 나타낸다. 반복 횟수 바이트의 최상위 비트는 1이며, 나머지 7비트에는 반복 횟수 - 3이 저장된다. 따라서 하나의 2바이트 run 표현은 같은 값이 3번부터 130번까지 반복되는 경우를 나타낼 수 있다. run의 최소 길이는 3이다.

run이 아닌 바이트들은 prefix 바이트와 그 뒤의 원래 바이트들로 인코딩한다. prefix 바이트의 최상위 비트는 항상 0이고, 나머지 값은 뒤따르는 run이 아닌 바이트의 개수 - 1이다. 따라서 prefix 바이트 하나는 1바이트부터 128바이트까지의 run이 아닌 데이터를 나타낼 수 있다.

길이가 130바이트를 넘는 run은 여러 개의 2바이트 run 표현으로 나눈다. 이때 앞쪽부터 가능한 한 길이 130인 run으로 인코딩한다. 같은 값이 3번 이상 반복되는 구간은 반드시 run으로 인코딩해야 한다. run이 아닌 구간이 128바이트보다 길면 prefix 바이트를 여러 개 사용한다. 예를 들어 길이 262인 run은 길이 130인 run 두 개와 길이 2인 run이 아닌 바이트 구간으로 인코딩한다.

첫째 줄에 데이터 세트의 수 P (1 <= P <= 1000)가 주어진다.

각 데이터 세트의 첫째 줄에는 바이트 수 B (1 <= B <= 5000)가 십진수 정수로 주어진다.

다음 줄부터 인코딩할 데이터가 주어진다. 데이터의 마지막 줄을 제외한 각 줄에는 16진수 문자 80개가 주어지며, 마지막 줄은 80개보다 짧을 수 있다. 16진수 문자 두 개가 한 바이트를 나타낸다. 각 16진수 문자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F 중 하나이다.

각 데이터 세트마다 먼저 인코딩된 바이트 수를 한 줄에 출력한다. 이어지는 줄에는 인코딩된 데이터를 16진수로 출력한다. 마지막 줄을 제외한 각 줄에는 16진수 문자 80개를 출력하고, 마지막 줄에는 80개 이하를 출력한다.