Vortex

Albert plays a game called "Vortex" on an $n \times n$ two-dimensional grid. For convenience, the cell in row $r$ and column $c$ of the board is written as $(r, c)$.

Each cell of the board contains one uppercase English letter ('A'-'Z'). For example, the left figure below shows a $3 \times 3$ board. Cell $(1, 2)$ contains "C" and cell $(3, 1)$ contains "G".
The right figure shows a $5 \times 5$ board. The outermost cells of this board contain "A" or "B" (16 cells in total). The innermost cell contains "Z". The remaining cells contain "X" or "Y" (8 cells in total).

Formally, the "outermost" to "innermost" cells of an $n \times n$ board are defined as follows.

• Cells lying in the first or last row or column are the "outermost" cells. In the $4 \times 4$ and $5 \times 5$ boards below, the cells marked "1" are the outermost cells.
• After removing all outermost cells, an $(n-2) \times (n-2)$ board remains. As above, the cells lying in the first or last row or column of the remaining board are the (second) outer cells. The cells marked "2" in the figure below are these.
• Continuing inward, we can define cells from the outermost to the innermost.

The Vortex game selects cells one at a time according to the following rules, for a total of $n^2$ cells.

1. First, choose one of the corner cells $(1, 1)$, $(1, n)$, $(n, 1)$, or $(n, n)$ to start. Then continue according to the rules below until every cell has been selected exactly once.

2. Repeatedly choose one of the cells adjacent (up, down, left, right) to the currently selected cell, according to the following rules:

   • Rule 1: A cell selected before cannot be selected again.
   • Rule 2: Among all cells that can be chosen without breaking Rule 1, you must choose a cell lying on the outermost layer of the board (if several such cells exist, you may choose any one of them).

A string (of length $n^2$) obtained by selecting all $n^2$ cells while following these rules is called a "vortex string".

For example, for the $3 \times 3$ board above, a vortex string can be obtained as follows:

• Turn 1: starting at $(1, 1)$:

  • By Rule 1, the only cells that can be chosen next are $(1, 2)$ or $(2, 1)$.
  • Both lie on the outermost layer of the board, so either may be chosen. In this example we choose $(1, 2)$.

• Turn 2: after choosing $(1, 2)$:

  • By Rule 1, the only cells that can be chosen next are $(1, 3)$ or $(2, 2)$.
  • Of these two, $(1, 3)$ lies farther out than $(2, 2)$, so by Rule 2 we must choose $(1, 3)$.

• Turn 3: after choosing $(1, 3)$:

  • By Rule 1, we must choose $(2, 3)$.

• Turns 4-9: after choosing $(2, 3)$, the rules force us to choose the remaining cells in the order $(3, 3)$, $(3, 2)$, $(3, 1)$, $(2, 1)$, $(2, 2)$.

• The vortex string obtained this way is "BCDFIHGEA".

• If on Turn 2 we choose $(2, 1)$ instead of $(1, 2)$, we obtain "BEGHIFDCA".

Starting at $(3, 3)$ on the same board gives different vortex strings:

• Choosing $(3, 2)$ after $(3, 3)$: "IFDCBEGHA"
• Choosing $(2, 3)$ after $(3, 3)$: "IHGEBCDFA"

We may also start at $(1, 3)$ or $(3, 1)$.

Albert wonders what the "maximum" and "minimum" vortex strings obtainable from a given board are.
For the example above, the maximum vortex string is "IHGEBCDFA" and the minimum is "BCDFIHGEA".

The maximum (minimum) vortex string is the lexicographically latest (earliest) string among all vortex strings obtainable in the Vortex game.

The first line of input gives the number of test cases $T$.

The first line of each test case gives the board size $n$.

The next $n$ lines each contain a string of length $n$.

For each test case, print the maximum vortex string and the minimum vortex string separated by a space, one per line.

• $1 \le T \le 10$
• $1 \le n \le 25$
• The board contains only uppercase English letters ('A'-'Z')