// Arup Guha
// 10/20/12 - 10/24/12
// Solution to Greater NY Regional Problem C: Encoding

import java.util.*;

public class c {

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);

		int numCases = stdin.nextInt();

		for (int loop = 1; loop<=numCases; loop++) {

			 // -1 means we haven't filled that square in yet.
			int r = stdin.nextInt();
			int c = stdin.nextInt();
			int[][] grid = new int[r][c];
			for (int i=0; i<r; i++)
				Arrays.fill(grid[i], -1);

			// Parse out string to encode.
			String s = stdin.nextLine();
			s = s.substring(1);
			
			// Move around the rectangle in a spiral.
			int dx = 0, dy = 1, x = 0, y = 0;
			for (int i=0; i<s.length(); i++) {

				// Set value.
				int val = 0;
				if (s.charAt(i) != ' ')
					val = (int)(s.charAt(i) - 'A' + 1);

				// Easier for us to peel off digits from the end, so reverse.
				val = rev5(val);
			
				// Place the next five bits.
				for (int j=0; j<5; j++) {
					grid[x][y] = val%2;

					// Take care of array out of bounds.
					if (x + dx >= r) {
						dy = -1; dx = 0;
					}
					else if (x + dx < 0) {
						dy = 1; dx = 0;
					}
					else if (y + dy >= c) {
						dy = 0; dx = 1;
					}
					else if (y + dy < 0) {
						dy = 0; dx = -1;
					}
					
					// This will work once we've spiraled in one level.
					else if (grid[x+dx][y+dy] != -1) {
						if (dx == 1) {
							dx = 0; dy = -1;
						}
						else if (dx == -1) {
							dx = 0; dy = 1;
						}
						else if (dy == 1) {
							dy = 0; dx = 1;
						}
						else {
							dy = 0; dx = -1;
						}
					}
					
					// Update for next move.
					x += dx;
					y += dy;
					val = val/2;
				}
			} // end s loop

			// Pad
			for (int i=0; i<r; i++)
				for (int j=0; j<c; j++)
					if (grid[i][j] == -1)
						grid[i][j] = 0;

			// Print result.
			System.out.print(loop+" ");
			for (int i=0; i<r; i++)
				for (int j=0; j<c; j++)
					System.out.print(grid[i][j]);
			System.out.println();

		}
	}

	// Assumes a is 5 bits and reverses its binary contents.
	public static int rev5(int a) {

		int ans = 0;
		for (int i=0; i<5; i++) {
			ans = ans*2 + a%2;
			a = a/2;
		}
		return ans;

	}
}