박테리아 (Small)

당신은 제약회사에서 일한다. 회사는 박테리아 샘플을 보관하려고 새 건물을 지었다. 건물은 여러 층으로 이루어지고, 각 층에는 직각다각형 모양의 방이 여러 개 있다. 모든 방에 샘플을 넣을 계획이었지만 설계에 치명적인 결함이 있었다. 천장과 바닥 사이의 마감이 완벽하지 않아서, 위아래로 맞닿은 두 방에 샘플을 함께 두면 서로 섞일 위험이 있다.

그래서 회사는 위아래로 인접한 두 방에는 샘플을 동시에 보관하지 않기로 했다. 샘플을 두지 않는 방에는 살균 설비를 설치해서 오염을 막는다. 이 조건을 지키면서 박테리아를 보관할 수 있는 방의 최대 개수를 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음 형식이다.

첫 줄에 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다. $N$은 한 층의 행 수, $M$은 한 층의 열 수, $K$는 층 수다. 이어서 각 층의 정보가 $K$개 주어지고, 한 층의 정보는 $N$개의 줄로 이루어진다. 층은 위아래로 맞닿은 순서대로 주어진다. 각 줄은 길이가 $M$인 문자열이고, .은 빈 칸, #은 벽을 뜻한다.

같은 층에서 가로나 세로로 맞닿은 빈 칸은 하나의 방에 속한다. 모서리에서만 닿는 칸은 서로 다른 방이다. 하나의 방이 두 개 이상의 층에 걸치는 경우는 없다. 예를 들어 아래 층에는 A, B, C 세 개의 방이 있다. 오른쪽은 각 칸이 어느 방에 속하는지 표시한 것이다.

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

$k$번째 층의 방과 $k+1$번째 층의 방은, 같은 행 같은 열의 칸이 두 층 모두에서 빈 칸이면서 각각 그 두 방에 속할 때 위아래로 인접하다.

제한

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

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 그 케이스에서 박테리아를 보관할 수 있는 방의 최대 개수다.