Bacteria (Small)

You work at a pharmaceutical company. The company put up a new building to store bacteria samples. The building has several floors, and each floor holds a number of rooms shaped like rectilinear polygons. The plan was to keep a sample in every room, but the design has a serious flaw. The seal between a ceiling and the floor above it is not tight, so two rooms that touch vertically let their samples mix when both hold a sample.

The company therefore decided never to store samples in two vertically adjacent rooms at the same time. Every room left without a sample gets sterilization equipment so that no contamination happens. Find the largest number of rooms that can hold bacteria under this rule.

The first line has the number of test cases $T$. Each test case has the following form.

The first line has three integers $N$, $M$, $K$ separated by spaces. $N$ is the number of rows on one floor, $M$ is the number of columns on one floor, and $K$ is the number of floors. Then the descriptions of $K$ floors follow, each made of $N$ lines. The floors come in the order they are stacked, so two consecutive descriptions are vertically adjacent floors. Each line is a string of length $M$ where . is an empty cell and # is a wall.

Empty cells that touch horizontally or vertically on the same floor belong to the same room. Cells that touch only at a corner belong to different rooms. No room spans two or more floors. For example, the floor below has three rooms A, B, C. The right side marks which room each cell belongs to.

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

A room on floor $k$ and a room on floor $k+1$ are vertically adjacent when some cell in the same row and the same column is empty on both floors and belongs to those two rooms.

Constraints

• $1 \le T \le 50$
• $1 \le N, M, K \le 5$

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