You are given a rectangular grid with rows and columns. Each cell of this grid is painted with one of two colors: green and white. Your task is to find the number of green cells in the largest Christmas tree in this grid.
To define a Christmas tree, first we define a good triangle as follows:
A good triangle with top point at row , column and height is an isoeles triangle consisting entirely of green cells and pointing upward. Formally, this means that: The cell (, ) is green, and for each from to inclusive, the cells in row from column to column are all green.
For example:
..#..
.####
#####
is a good triangle with height 3. The # cells are green and the . cells are white. Note that there is a green cell that is not part of the good triangle, even though it touches the good triangle.
..#..
.###.
####.
is NOT a good triangle, because the 5th cell in the 3rd row is white. However, there are good triangles with height 2 present.
...#.
.###.
#####.
is NOT a good triangle. However, there are good triangles with height 2 present.
A K-Christmas tree is defined as follows:
It contains exactly good triangles in vertical arrangement.
The top cell of the -th triangle must share its top edge with the bottom edge of any one of the cells at the base of the -th triangle. This means that, if the base of the -th triangle is at row , from column to column , then the top of the -th triangle must be on row , in a column somewhere between and , inclusive.
is NOT a valid Christmas tree, because the 2nd triangle must starts from the 4-th row.
...#.
..###
.#...
###..
is NOT a valid Christmas tree, because the top of the 2nd triangle must be in a column between 3 and 5, inclusive.
You need to find the K-Christmas tree with the largest number of green cells.
输入格式
The first line of the input gives the number of test cases, . test cases follow. Each test case consists of three lines:
The first line contains 3 space-separated integers , and , where is the number of rows of the grid, is the number of columns of the grid and is the number of good triangle in the desired Christmas tree.
The next lines each contain exactly characters. Each character will be either . or #, representing a white or green cell, respectively.
输出格式
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of green cells in the largest K-Christmas tree. If there is no K-Christmas tree, output 0.
