Welcome to ZOJ
64 - The 8th Zhejiang University Programming Contest - 1002
Beautiful Meadow

Time Limit: 10 Seconds      Memory Limit: 32768 KB

Tom's Meadow

Tom has a meadow in his garden. He divides it into N * M squares. Initially all the squares are covered with grass and there may be some squares that can't be mowed. (Let's call them forbidden squares.) He wants to mow down the grass on some of the squares. He considers a meadow beautiful if and only if all these 8 rules are satisfied:
1 Not all squares are covered with grass.
2 Not all squares are mowed.
3 All the forbidden squares should not be mowed.
4 All the mowed squares are connected to each other.
5 All the squares covered by grass are connected to each other.
6 There's no 2*2 blocks in the meadow which consists of only mowed squares.
7 There's no 2*2 blocks in the meadow which consists of only squares covered by grass.
8 The number of mowed squares does not exceed K.
Two squares are adjacent if they share an edge.

Here comes the problem. How many patterns of beautiful meadows he can get?


This problem has several test cases. The first line of the input is a single integer T (1 <= T < 40) which is the number of test cases. And it will be followed by T consecutive test cases.

The first line of each test case is a single line containing 3 integers N (1 <= N <= 9) , M (1 <= M <= 9) and K (1 <= K <= N * M) which is the number of rows of the meadow, the number of columns of the meadow and the number of squares you can mow at most. Then N lines of input describe the rows of the meadow. Each of the N lines contains M space-separated signs "+" or "-" indicating whether the square can be mowed or not.


For each test case output an integer in a single line which is the number of the beautiful patterns.

Sample Input

1 1 1
1 2 2
+ +

Sample Output


The meadow contains only 1 square. No matter you mow down the grass or not, you cannot make the meadow beautiful because of rule 1 and 2.
The meadow contains 2 squares. You can mow down the grass of any one square to make it beautiful.

Submit    Status