Kyuhyun's Secret Text Message

Interview

Time limit1sMemory limit128 MB

Summary
Convert each character to a 5-bit code, fill an R by C matrix in clockwise spiral order with the concatenated bits (padding with zeros), then print the matrix read row by row.
Level

Medium4 of 10

Topics
Matrix, Simulation, Implementation
Solved
No attempts yet

Problem

Kyuhyun often sends Seunghwan text messages. To keep those messages private, they agreed to encode them with a secret rule.

For each message, Kyuhyun chooses a matrix with R rows and C columns. The message contains only uppercase English letters and spaces. Each character is converted to a number as follows:

  1. Space = 0
  2. A = 1, B = 2, ..., Y = 25, Z = 26

Each number is then written as a 5-bit binary string. The resulting bits are placed into the R x C matrix in clockwise spiral order, starting at the upper-left cell and initially moving to the right. If the message bits do not fill all cells, the remaining cells are filled with 0.

After the matrix is filled, read it in row-major order and output the resulting bit string.

Given R, C, and Kyuhyun's message, write a program that produces the encoded secret message.

Input

The first line contains the number of test cases T (1 <= T <= 1,000).

Each test case is given on one line in the form R, a space, C, a space, and the message to encode (1 <= R, C <= 21). The message consists only of uppercase English letters and spaces, and its length is always at most (R * C) / 5.

Output

For each test case, output the encoded secret message that Kyuhyun will send.

Examples1

  1. Example 1

    Input
    4
4 4 ACM
5 2 HI
2 6 HI
5 5 HI HO
    Expected output
    0000110100101100
0110000010
010000001001
0100001000011010110000010