Baltic Olympiad in Informatics: 2016 Day 2, Problem 2

Uolevi has developed a game where the player collects coins in a maze. At the moment, the problem is that the game is too easy. Could you design some challenging mazes for the game?

Each maze is a rectangular grid that consists of floors (.) and walls (#). One of the cells is a base (x), and some cells can contain coins (o). The player begins in the base, and can move left, right, up and down. The task of the player is to collect all coins in the maze and then return to the base.

The difficulty of a maze is the length of the shortest path that begins in the base, collects all coins and returns to the base.

Grading

For each maze, your score is $max(0,100-3(d-x))$ where $x$ is the difficulty of your maze and $d$ is the difficulty of the most challenging maze found by the jury. Your total score for the task is the average of all scores rounded down to an integer.

Input Specification

The input begins with an integer $t$: the number of mazes. After this, $t$ lines follow. Each such line contains three integers $n$, $m$ and $k$. This means that the size of the maze must be $n\times m$ cells and there must be exactly $k$ coins.

Output Specification

The output should contain $t$ maze descriptions, separated by empty lines, in the same order as in the input. Each maze must be solvable.

Sample Input

2
3 3 1
4 7 2

Sample Output

###
#.x
#o#

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

The difficulty of the first maze is $4$, and the difficulty of the second maze is $18$.

Input

This is an output only task and there is only one input file provided below. You have to submit an output file that contains all the mazes specified in the input file below.

50
10 18 2
11 14 3
9 17 4
8 9 6
5 11 4
10 20 5
9 10 8
7 6 9
12 20 6
12 20 12
8 14 8
11 18 4
14 5 7
12 11 4
18 6 6
9 17 6
10 13 4
8 13 6
12 12 5
11 5 5
13 12 11
13 13 6
7 15 8
5 5 4
12 9 12
7 17 10
12 16 2
10 10 4
10 20 6
19 11 10
14 13 6
17 13 8
7 19 1
8 16 8
14 9 12
13 9 2
16 5 2
7 10 1
13 17 6
18 7 11
16 13 1
16 13 12
11 12 3
15 9 5
13 19 12
5 17 1
8 16 8
6 6 10
20 13 2
11 7 3