Uolevi 开发了一款玩家在迷宫中收集硬币的游戏。目前的问题是游戏太简单了。你能为这款游戏设计一些具有挑战性的迷宫吗？

每个迷宫都是一个由地板（.）和墙壁（#）组成的矩形网格。其中一个单元格是基地（x），一些单元格包含硬币（o）。玩家从基地出发，可以向左、向右、向上、向下移动。玩家的任务是收集迷宫中的所有硬币，然后返回基地。

迷宫的难度定义为从基地出发，收集所有硬币并返回基地的最短路径长度。

输入格式

输入的第一行包含一个整数 $t$，表示迷宫的数量。接下来有 $t$ 行，每行包含三个整数 $n, m$ 和 $k$。这意味着迷宫的大小必须为 $n \times m$ 个单元格，且必须恰好包含 $k$ 个硬币。

输出格式

输出应包含 $t$ 个迷宫描述，以空行分隔，顺序与输入一致。每个迷宫必须是可解的。

样例

输入格式 1

2
3 3 1
4 7 2

输出格式 1

###
#.x
#o#

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

说明

第一个迷宫的难度为 4，第二个迷宫的难度为 18。

实现细节

这是一个仅输出任务。你可以下载输入文件。你需要提交一个包含输入文件中指定的所有迷宫的输出文件。

评分

对于每个迷宫，你的得分为 $\max(0, 100 - 3(d - x))$，其中 $x$ 是你设计的迷宫的难度，$d$ 是评委找到的最具挑战性的迷宫的难度。你在此任务中的总分为所有得分的平均值，向下取整。