Maze Coin Collection Construction

You are given a maze represented as a grid of size \(n \times m\). The maze consists of four types of cells:

• . - Floor (walkable)
• # - Wall (not walkable, cannot be passed through)
• x - Base
• o - Coin

Your task is to construct a maze such that starting from the base cell, by moving up, down, left, or right, and eventually returning to the base, the maximum number of coins collected is exactly \(k\). Note that a coin in a cell can only be collected once, even if the cell is visited multiple times.

You are given \(t\) test cases. For each test case, you are provided with three integers \(n\), \(m\), and \(k\) (with \(1 \le k \le n \times m - 1\)), and you need to construct a maze that meets the above requirement. The maze must contain exactly one base cell marked as x and exactly \(k\) coins (all other walkable cells are marked as .). You can fill other cells with . so that the maze remains fully connected.

Note: It is guaranteed that a solution exists for the given constraints.

inputFormat

The first line contains an integer \(t\) representing the number of test cases.

Each of the following \(t\) lines contains three integers \(n\), \(m\), and \(k\) separated by spaces, where \(n\) and \(m\) are the dimensions of the maze and \(k\) is the required maximum number of coins collectable through a cycle starting and ending at the base.

It is guaranteed that \(1 \leq k \leq n \times m - 1\).

outputFormat

For each test case, output \(n\) lines each containing a string of length \(m\) representing the constructed maze. The maze must have exactly one base cell marked with x and exactly \(k\) coin cells marked with o. All other walkable cells should be marked as . (floor). Walls (if any) are marked with #, but in your construction, you may use only walkable cells if it satisfies the condition.

sample

1
3 3 2

xoo
...
...