동전 미로

Uolevi는 미로에서 동전을 모으는 게임을 만들었다. 지금은 게임이 너무 쉽다. 미로를 직접 만들어야 한다.

미로는 세로 $n$칸, 가로 $m$칸인 격자이다. 각 칸은 바닥(.)이거나 벽(#)이다. 칸 하나에는 기지(x)가 있고, 정확히 $k$개의 칸에는 동전(o)이 있다.

플레이어는 기지에서 시작한다. 상하좌우로 한 칸씩 이동하며 벽으로는 가지 못한다. 모든 동전을 모은 다음 기지로 돌아와야 한다. 그런 경로가 있으면 그 미로는 풀 수 있다.

같은 $n$, $m$, $k$로 풀 수 있는 미로는 여러 개일 수 있다. 아래 규칙으로 정한 미로만 출력한다.

$(n, m, k) = (3, 3, 1)$이면 다음 미로를 출력한다.

###
#.x
#o#

$(n, m, k) = (4, 7, 2)$이면 다음 미로를 출력한다.

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

그 밖의 $(n, m, k)$에서는 다음을 따른다.

1. 모든 칸을 .으로 채운다.
2. 왼쪽 위 칸(1행 1열)에 x를 둔다.
3. 기지를 건너뛰고, 행 우선 순서(각 행은 왼쪽에서 오른쪽, 행은 위에서 아래)로 다음 $k$개의 칸에 o를 둔다.

이 격자에는 벽이 없으므로 플레이어는 모든 동전에 도달한 뒤 기지로 돌아올 수 있다.

첫째 줄에 정수 $t$가 주어진다. 만들어야 할 미로의 개수이다.

다음 $t$개 줄 각각에 정수 $n$, $m$, $k$가 주어진다. 미로 크기는 $n \times m$이고 동전은 정확히 $k$개이다.

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

입력과 같은 순서로 미로 $t$개를 출력한다. 이웃한 두 미로 사이에는 빈 줄을 하나 둔다.

각 미로는 $n$줄이고, 각 줄은 길이 $m$인 문자열이다. 문자는 #, ., o, x 중 하나이다. 기지는 정확히 하나이고 동전은 정확히 $k$개여야 한다. 미로는 풀 수 있어야 한다.

$(3, 3, 1)$ 미로에서 플레이어는 기지에서 왼쪽으로 한 칸, 아래로 한 칸 가서 동전을 줍고 같은 길로 돌아온다. 이동 횟수는 4이다.

$(4, 7, 2)$ 미로에서 두 동전을 모두 모으고 기지로 돌아오는 최단 경로의 길이는 18이다.

일반 규칙으로 만든 미로는 모든 칸이 바닥이므로 항상 풀 수 있다.