490. Figure ans Spots
Time limit per test: 0.25
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
Let's consider an infinite sheet of grid paper. Initially all the cells are white and you can paint some of them black.
Two cells are called 8neigbours if they share a side or a corner. An 8path between black cells
A and
B is a sequence of cells
X_{0} =
A,
X_{1}, ·s,
X_{L1},
X_{L} =
B such that all cells in the sequence are black and for all 0 ≤
i <
L the cells
X_{i} and
X_{i+1} are 8neighbours. A set of black cells is called a figure if there is an 8path from each of them into each other.
Two cells are called 4neighbours if they share a side. A 4path between white cells
A and
B is a sequence of cells
X_{0} =
A,
X_{1}, ·s,
X_{L1},
X_{L} =
B such that all cells in the sequence are white and for all 0 ≤
i <
L the cells
X_{i} and
X_{i+1} are 4neigbours. A finite set of white cells is called a
if:
 There is a 4path from each of them into each other.
 The previous condition is broken when any other white cell is added to the set.
We say that a figure has the height
H and the width
W if it fits in a rectangle
H rows high and
W columns wide, but does not fit in a rectangle
H1 rows high and
W columns wide nor in a rectangle
H1 rows high and
W columns wide.
The image above shows a figure with height 7 and width 9 and containing two spots.
Given the numbers
H,
W and
N, construct a figure with height exactly
H and width exactly
W and containing exactly
N spots.
Input
The input file contains several test cases. The first line of the file contains
T (1 ≤
T ≤ 100), the number of test cases. Each of the following
T lines describes one test case and contains three integers
H,
W and
N (1 ≤
H,
W ≤ 20, 1 ≤
N ≤ 200), separated by spaces.
Output
The output file should contain the following data for each test case:
 If it is possible to construct a figure with the given parameters, output any of the possible figures as H rows consisting of W characters each; output the character
.
for a black cell and the character #
for a white cell.  If it is impossible to construct the required figure, output a single line containing the word .
The output data for two different test cases should be separated by an empty line.
Example(s)
sample input

sample output

3
7 9 2
20 20 22
5 5 10

#......##
#.#.....#
#.##.....
....####.
.#..##.#.
.#..##.#.
.#.......
.#####.######.#####.
..###...####...###..
...#.....##.....#...
....................
....##..##..#...#...
...#.#.#..#.##.##...
...###.#....#.#.#...
...#.#.#..#.#...#...
...#.#..##..#...#...
....................
....................
.###..##..###...##..
..#..#..#.#..#.#..#.
..#..#....###..#....
..#..#..#.#....#..#.
.###..##..#.....##..
....................
...#.....##.....#...
..###...####...###..
.#####.######.#####.
Impossible
