C. Gas Reservoir
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Consider a three-dimensional grid of size $$$X \times Y \times Z$$$, representing underground layers. The $$$(x, y)$$$ plane corresponds to the horizontal surface, while the $$$z$$$-axis represents depth below the surface, with $$$z = 0$$$ denoting the topmost layer.

Each cell of the grid is of exactly one of the following two types:

  • Rock: denoted by the character '#'.
  • Gas: denoted by the character '.', where each gas cell contains exactly $$$1$$$ unit of gas.

A reservoir is defined as a maximal connected component of gas cells. Two gas cells are considered adjacent if and only if they share a common face. More formally, a gas cell with coordinates $$$(x, y, z)$$$ is adjacent to another gas cell if their coordinates differ by exactly $$$1$$$ in one of the three dimensions and are equal in the other two dimensions; that is, the adjacent coordinates are $$$(x \pm 1, y, z)$$$, $$$(x, y \pm 1, z)$$$, or $$$(x, y, z \pm 1)$$$.

You may dig a borehole from the surface. A borehole is defined by choosing a surface coordinate $$$(x, y)$$$ and drilling vertically downward through all depths from the top layer $$$(z = 0)$$$ to the bottom layer $$$(z = Z - 1)$$$.

During drilling, the drill passes through both rock and gas cells. Whenever the drill encounters a gas cell, it immediately collects the entire reservoir containing that cell. Drilling continues downward and may intersect multiple reservoirs at different depths. Each reservoir is collected at most once, even if the drill intersects it multiple times within the same vertical column. Each gas cell contributes exactly $$$1$$$ unit to the total collected gas.

Thus, drilling a borehole at surface coordinates $$$(x, y)$$$ collects the total amount of gas contained in all distinct reservoirs that include at least one gas cell in the vertical column $$$(x, y, 0), (x, y, 1), \dots, (x, y, Z - 1)$$$.

Your task is to determine the maximum total amount of gas that can be collected by drilling a single borehole at an optimal choice of surface coordinates $$$(x, y)$$$.

Input

The first line of the input contains a single integer $$$T (1 \le T \le 10)$$$ — the number of test cases.

The first line of each test case is a blank line. The second line of each test case contains three space-separated integers $$$X$$$, $$$Y$$$ and $$$Z$$$ $$$(1 \le X, Y, Z \le 50)$$$ — the dimensions of the grid. The third line of each test case is a blank line. Then follow $$$Z$$$ layers, from top ($$$z = 0$$$) to bottom ($$$z = Z - 1$$$).

Each layer consists of $$$X$$$ lines, each containing a string of length $$$Y$$$, consisting only '#' (rock) and '.' (gas). Consecutive layers are separated by a blank line.

Output

For each test case, output a single integer in a line — the maximum total number of gas units that can be collected by drilling exactly one borehole.

Example
Input
2

2 2 3

.#
#.

..
..

##
#.

1 2 2

.#

#.
Output
7
1