Bacteria (Large)

Problem

You work at a pharmaceutical company. The company recently put up a building to store bacteria samples. The building has several floors, and each floor holds several rooms shaped as rectilinear polygons.

The company planned to store a sample in every room, but the design has a serious flaw. The seal between a ceiling and the floor above it is imperfect, so samples placed in two rooms that are adjacent from one floor to the next can mix.

The company therefore decided never to store bacteria in two rooms that are adjacent from one floor to the next. Every room left without bacteria gets sterilization equipment so that no contamination happens. Find the largest number of rooms in this building that can hold bacteria under that rule.

Input

The first line has the number of test cases $T$ . $T$ test cases follow.

The first line of a test case has the number of rows $N$ on one floor, the number of columns $M$ on one floor, and the number of floors $K$ , separated by spaces. The plans of the $K$ floors follow, starting from the first floor. The plan of one floor is $N$ lines of $M$ characters each. A . means the cell is empty and a # means the cell is a wall.

Empty cells that touch horizontally or vertically on the same floor belong to the same room. For example, the floor below has three rooms, A, B and C.

#..#      #AA#
###.      ###B
..#.      CC#B
#..#      #CC#

No room spans two or more floors. Two rooms on two floors that touch each other are adjacent from one floor to the next when they share at least one empty cell with the same row and the same column.

Constraints

$1 \le T \le 50$
$1 \le N, M \le 20$
$1 \le K \le 50$

Output

For each test case, print one line in the form Case #x: y. $x$ is the test case number starting from 1, and $y$ is the largest number of rooms that can hold bacteria in that case.