시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB40191744.737%

문제

당신은 한 제약회사에서 근무하고 있다. 이 제약회사는 최근 박테리아 샘플을 보관하기 위해서 건물을 지었는데, 이 건물은 여러 층으로 이루어져 있으며 각 층에는 직각 다각형 모양의 방들이 있다. 회사는 이 건물의 모든 방에 박테리아 샘플을 보관하려고 계획했지만, 건물 설계상의 치명적 결함이 발견되어서 그럴 수 없게 되었다. 천장과 바닥 사이의 마감이 완벽하지 못해서 위아래로 인접한 방 양쪽에 박테리아 샘플이 있다면 둘이 서로 섞일 위험이 발견된 것이다. 이 문제 때문에 회사는 위아래 층으로 서로 인접한 방에는 동시에 박테리아를 보관하지 않기로 했고, 박테리아를 보관하지 않는 방에는 살균 설비를 설치해서 오염이 일어나지 않도록 조치하려고 한다. 당신의 임무는 조건을 만족하면서 이 건물에서 최대 몇 개의 방에 박테리아를 보관할 수 있는지 알아내는 것이다.

입력

입력의 첫 줄에는 테스트 케이스의 숫자 T가 주어진다. 아래로는 T개의 테스트 케이스가 다음과 같이 주어진다. 

N M K
B1,1,1B1,2,1 … B1,M,1
B2,1,1B2,2,1 … B2,M,1
…
BN,1,1BN,2,1 … BN,M,1
…
BN,1,KBN,2,K … BN,M,K

여기서 N은 건물 한 층의 행 수, M은 건물 한 층의 열 수, K는 건물의 층 수를 나타낸다. Bi,j,k는 ‘.’ 인 경우 해당 칸이 비어있음을, ‘#’인 경우 해당 칸이 벽임을 나타내며, 한 층에서 가로/세로로 인접한 빈 칸들은 하나의 방에 속한다. 예를 들어 다음과 같은 구조의 층에는 A, B, C 세 개의 방이 있다. 하나의 방이 두 개 이상의 층에 걸쳐있는 경우는 없다.

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

제한

  • 1 ≤ T ≤ 50.
  • 1 ≤ NM ≤ 20.
  • 1 ≤ K ≤ 50.

출력

각 테스트 케이스에 대한 출력은 "Case #x: y" 형태로 이루어져야 한다. x는 1부터 시작되는 케이스 번호이고, y는 해당 케이스에 대해서 박테리아를 보관할 방의 최대 숫자이다.

예제 입력 1

3
3 3 3
...
###
...
.##
.#.
.#.
.##
###
.##
4 4 2
.#..
#.#.
.#..
#.#.
.#.#
..#.
.#.#
..#.
1 5 3
...##
.#.#.
##...

예제 출력 1

Case #1: 4
Case #2: 8
Case #3: 3 

채점 및 기타 정보

  • 예제는 채점하지 않는다.