거울의 방

당신은 2차원 평면에 살고 있으며, 즐겨 방문하는 장소 중 하나는 Hall of Mirrors이다. 거울의 방은 격자 형태로 배치된 방(물론 2차원 방)이다. 격자의 모든 칸에는 정사각형 거울, 빈 공간, 또는 당신이 있다. 너비는 0, 높이는 0이며, 당신은 자신의 격자 칸 정중앙에 있다.

몸집이 매우 작지만, 당신의 모습이 정확히 자신에게 되반사되면 자신의 상을 볼 수 있다. 예를 들어, '#'는 해당 칸을 완전히 채우는 정사각형 거울을 나타내고, '.'는 빈 공간을 나타내며, 대문자 'X'는 당신이 해당 칸의 중앙에 있음을 나타내는 다음 배치를 살펴보자.

######
#..X.#
#.#..#
#...##
######

똑바로 위쪽이나 똑바로 오른쪽을 바라보면 자신의 상을 볼 수 있다.

안타깝게도 Hall of Mirrors에는 안개가 매우 짙어서 D단위보다 멀리 볼 수 없다. D=3라고 하자. 위쪽을 바라보면 자신의 상은 1단위 떨어져 있다(거울까지 0.5, 되돌아오는 데 0.5). 오른쪽을 바라보면 자신의 상은 3단위 떨어져 있고(거울까지 1.5, 되돌아오는 데 1.5), 그 상을 볼 수 있다. 아래쪽을 바라보면 자신의 상은 5단위 떨어져 있어 볼 수 없다.

Hall of Mirrors에서 빛이 어떻게 이동하는지 이해하는 것이 중요하다. 빛은 거울에 부딪힐 때까지 직선으로 이동한다. 빛이 거울의 모서리를 제외한 어느 부분에든 부딪히면 일반적인 방식으로 반사된다. 즉, 반사각이 입사각과 같게 튕겨 나간다. 반면 빛이 거울의 모서리에 닿게 되는 경우에는 상황이 더 복잡하다. 다음 그림들은 각 경우를 설명한다.

다음 경우에는 빛이 모서리에 접근한 뒤 반사되어 방향이 바뀐다. 처음 두 경우에는 빛이 서로 인접한 두 거울이 맞닿는 지점으로 접근했다. 빛은 긴 거울의 가운데에 부딪힌 것과 같은 방식으로 반사되었다. 세 번째 경우에는 빛이 서로 인접한 세 거울의 모서리로 접근했고, 정확히 자신이 온 방향으로 되돌아갔다.

다음 경우에는 빛이 하나 이상의 거울 모서리에 접근하지만 튕기지 않고, 대신 같은 방향으로 계속 이동한다. 이는 빛이 거울의 모서리에서 거리 0인 지점에 도달하지만, 같은 방향으로 계속 이동하기 위해 거울을 통과할 필요는 없을 때 발생한다. 이런 방식으로 광선은 대각선으로 서로 인접한 두 거울 사이를 지나갈 수 있다. 실질적으로 크기가 0인 공간을 통과하는 것이다. 다행히 광선의 크기도 0이므로 들어맞는다!

마지막 경우에는 빛이 한 거울의 모서리에 접근한 뒤 소멸한다. 거울이 빛의 경로에 있었고, 광선은 다른 어떤 거울의 모서리에도 접근하지 않았다.

빛은 당신에게 부딪히면 멈추지만, 반드시 당신이 있는 격자 칸의 정중앙에 부딪혀야 한다는 점에 유의하라.

자신의 상을 몇 개 볼 수 있는가?

제한

메모리 제한: 1GB. 테스트 세트당 시간 제한: 60초. 1 ≤ T ≤ 100. 3 ≤ H, W ≤ 30. 1 ≤ D ≤ 50. 각 지도에 있는 모든 문자는 '#', '.', 또는 'X'이다. 각 지도에는 정확히 하나의 'X' 문자가 있다. 각 지도의 첫 번째 행, 마지막 행, 첫 번째 열, 마지막 열은 모두 '#' 문자로 채워져 있다.

테스트 세트 1 (Visible Verdict)

'#' 문자는 최대 2W+2H-4개이다.

테스트 세트 2 (Hidden Verdict)

소규모 데이터 세트의 제한은 적용되지 않는다.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 세 정수 H, W, D가 포함된 한 줄로 시작한다. 이어서 H개의 줄이 주어지며, 각 줄에는 W개의 문자가 있다. 이 문자들은 위에서 설명한 해당 테스트 케이스의 Hall of Mirrors 지도를 구성한다.

각 테스트 케이스마다 "Case #x: y"이 포함된 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 볼 수 있는 자신의 상의 개수이다.

첫 번째 경우에 똑바로 위쪽, 아래쪽, 왼쪽 또는 오른쪽을 바라보면 빛은 정확히 거리 1만큼 이동한다.

두 번째 경우에 오른쪽 위, 왼쪽 위, 오른쪽 아래 또는 왼쪽 아래를 바라보면 빛은 거리 1.414...만큼 이동한다. 빛은 당신을 통과하지 않으므로 똑바로 위쪽을 바라보면 자신의 상이 하나만 보인다.

다섯 번째 경우에는 가까운 거울이 빛을 당신에게 되돌려 반사할 수 있을 만큼 가깝지만, 거울의 모서리에 부딪힌 빛은 반사되지 않고 소멸한다.