Pop the Balloons

Recently, an interesting balloon-popping game can be commonly found near the streets. The rule of this game is quite simple: some balloons are tied to cells of an $n \times m$ lattice, and you are allowed to throw $k$ darts to prick the balloons. The more balloons you pierce, the more incredible prize you will get.

Probably because too many people have got bored with this childish game, a new variation of the game has appeared. In this variation, the balloons are replaced with more powerful ones: when a balloon explodes, strong gusts travel in four directions, blowing away all remaining balloons in the same row and column. In order to reduce the difficulty, not all cells are filled with a balloon.

For example, if you prick the yellow balloon in the following figure, then the red balloons will be blown away, with only the blue balloon remaining.



Now, you are given $k$ darts. Since you are a good dart player that you can precisely throw it to any position you want, it is easy for you to use these $k$ darts to clear all balloons (either by directly pricking, or by blowing away by other exploded balloons). Now you begin to consider: for every $1 \leq x \leq k$, how many different ways are there to clear all balloons with exactly $x$ darts? Two ways are considered different if and only if there exists $i$, such that the positions of $i$-th pricked balloons differ. Note that you cannot throw the dart to an empty cell.

The first line of input is a single integer $T$ $(1 \leq T \leq 100)$, denoting the number of test cases.

Each test case begins with a line of three integers $m, n$ $(1 \leq m \leq 12, 1 \leq n \leq 20)$, denoting the size of the balloon lattice, and $k$ $(1 \leq k \leq 20)$, denoting the number of darts. The next $m$ lines, each containing $n$ characters, describe the balloon lattice. Each character is either $\texttt{'Q'}$, which denotes a balloon, or $\texttt{'.'}$, which denotes an empty cell.

For each test case, display $k$ lines. The $i$-th line is a single integer denoting the number of different ways of clearing all balloons with exactly $i$ darts.

4
2 2 2
QQ
.Q
2 2 2
QQ
..
3 3 3
.Q.
QQQ
.Q.
1 3 1
Q.Q

1
2
2
0
1
8
0
2

2018 Multi-University Training Contest 8