박테리아 (Large)

당신은 제약회사에서 일한다. 이 회사는 박테리아 샘플을 보관하려고 최근에 건물을 새로 지었다. 건물은 여러 층으로 이루어지고, 각 층에는 직각 다각형 모양의 방이 여러 개 있다.

회사는 이 건물의 모든 방에 박테리아 샘플을 보관할 계획이었지만, 설계에 치명적인 결함이 있어서 그럴 수 없게 되었다. 천장과 바닥 사이의 마감이 완벽하지 않아서, 위아래로 인접한 두 방에 샘플을 함께 두면 둘이 서로 섞일 위험이 있다.

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

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 한 층의 행 수 $N$, 한 층의 열 수 $M$, 건물의 층 수 $K$가 공백으로 구분되어 주어진다. 그다음 $K$개 층의 평면도가 1층부터 순서대로 주어진다. 한 층의 평면도는 각각 $M$개의 문자로 이루어진 $N$개의 줄이다. 문자가 .이면 그 칸은 비어 있고, #이면 그 칸은 벽이다.

같은 층에서 가로나 세로로 맞닿은 빈 칸은 같은 방에 속한다. 예를 들어 다음 층에는 방이 A, B, C로 세 개 있다.

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

하나의 방이 두 층 이상에 걸치는 경우는 없다. 서로 맞닿은 두 층에 있는 두 방이 행과 열이 같은 빈 칸을 하나 이상 공유하면, 두 방은 위아래로 인접하다.

제한

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

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