Coin maze

Uolevi made a game where the player collects coins in a maze. The game is too easy. You must design the mazes.

Each maze is a grid with $n$ rows and $m$ columns. Each cell is a floor (.) or a wall (#). Exactly one cell is the base (x). Exactly $k$ cells hold coins (o).

The player starts at the base and moves one cell up, down, left, or right. Walls cannot be entered. The player must collect every coin and then return to the base. A maze is solvable when such a route exists.

Several solvable mazes can exist for the same $n$, $m$, and $k$. Print only the maze fixed by the rules below.

If $(n, m, k) = (3, 3, 1)$, print this maze.

###
#.x
#o#

If $(n, m, k) = (4, 7, 2)$, print this maze.

.o.####
.#..x.#
...##.#
###o...

For every other triple $(n, m, k)$, build the maze as follows.

1. Fill every cell with ..
2. Put x in the upper-left cell (row 1, column 1).
3. Skipping the base, put o on the next $k$ cells in row-major order (left to right in each row, rows from top to bottom).

This grid has no walls, so the player can reach every coin and return to the base.

The first line contains an integer $t$: the number of mazes to build.

Each of the next $t$ lines contains three integers $n$, $m$, and $k$. The maze must have $n \times m$ cells and exactly $k$ coins.

• $t \ge 1$
• $n \ge 1$, $m \ge 1$
• $k \ge 1$
• $k + 1 \le n \times m$

Print $t$ mazes in the same order as the input. Put one empty line between neighboring mazes.

Each maze has $n$ lines, and each line is a string of length $m$. Each character is #, ., o, or x. There must be exactly one base and exactly $k$ coins. Each maze must be solvable.

In the $(3, 3, 1)$ maze the player steps left from the base, then down to the coin, and returns along the same cells. That route has length 4.

In the $(4, 7, 2)$ maze the shortest route that collects both coins and returns to the base has length 18.

A maze built by the general rule has only floors, so it is always solvable.