1997 Woburn Computer Programming Challenge

A kind of grid is sometimes used for encoding messages. Our naval fleet (!) officials decide to use this method of encoding messages for communication with their ship captains. The encoding grid is a square sheet of paper divided into ~2N \times 2N~ little squares. ~N^2~ of these little squares are cut out (see figure 1).

Let us briefly describe the encoding process. Take a message of length ~4N^2~ characters. Then put an encoding grid onto a blank sheet of paper and begin to write the first ~N^2~ letters of the message into the cut-out squares (one letter per square, write letters in the first line from left to right, then in the second line, etc.) See figure 2 for the first step in the message HELLOYELLOWWORLD. After finishing the first step rotate the encoding grid 90 degrees clockwise and continue similarly writing letters. (Figures 3, 4)

After two more steps, all of the letters should be written in (figure 5).

It is necessary to have a correctly constructed grid, so that we never get a collision (i.e. we see some already-written letters through holes in the grid after we rotate). We need to always see ~N^2~ blank squares after we rotate the grid.

The naval fleet officials encoded thousands of messages with their grid and then they wanted to send them to ships. Unfortunately, they lost the grid. Fortunately, the naval admiral remembered the original text of one of the messages.

Your task is, given this original message text and the filled-in piece of paper with this encoded message, to find one possible correctly constructed grid with which the message text could have been encoded.

Input Specification

The first line of input contains an integer ~M~ specifying the number of test cases.
The first line of each test case is ~N~ (the encoded message is written on a ~2N \times 2N~ grid).
~N~ will be an integer between 1 and 10 inclusive.

The second line of each test case is the message which was encoded: a string of ~4N^2~ characters.
Each of the next ~2N~ lines contains a string of ~2N~ characters representing the letters in the encoded grid. This grid contains only letters from A to Z.

Output Specification

The output file should contain one correctly constructed grid for each test case which could have been used to encode the given message into the given grid. The grid should appear in the orientation in which the first ~N^2~ letters are written. As in figure 1 above, represent uncut parts of the paper with # and holes with O (the capital letter, not the number). Leave a blank space between the output for each test case; you may leave a trailing blank line at the end of your output file.

Sample Input

2
2
HELLOYELLOWWORLD
HOOY
LREO
LWEL
LLDW
1
SUNK
SU
KN

Sample Output

O###
##O#
O##O
####

O#
##