거울의 방 (큰 입력)

문제

당신은 2차원 평면에 살고, 가장 좋아하는 장소 중 하나가 거울의 방이다. 거울의 방은 격자로 나뉜 방이고, 물론 2차원이다. 격자의 각 칸에는 정사각형 거울이 있거나, 빈 공간이거나, 당신이 서 있다. 당신의 너비와 높이는 0이고, 자기 칸의 정확한 중심에 서 있다.

이렇게 작아도 빛이 정확히 되돌아오면 자기 모습이 보인다. 아래 지도에서 #는 칸을 가득 채운 거울, .는 빈 공간, X는 당신이 중심에 서 있는 칸이다.

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

똑바로 위나 똑바로 오른쪽을 보면 자기 모습이 보인다.

거울의 방은 안개가 짙어서 $D$ 단위보다 먼 것은 보이지 않는다. $D = 3$ 이라고 하자. 위를 보면 반사된 자기 모습까지의 거리가 1이다 (거울까지 0.5, 되돌아오는 데 0.5). 오른쪽을 보면 거리가 3이므로 (가는 데 1.5, 오는 데 1.5) 역시 보인다. 아래를 보면 거리가 5라서 보이지 않는다.

빛은 거울을 만날 때까지 직선으로 나아간다. 거울의 꼭짓점이 아닌 부분에 닿으면 입사각과 반사각이 같게 반사된다. 거울의 꼭짓점에 정확히 닿는 경우는 규칙이 나뉜다.

다음 경우에는 빛이 꼭짓점에서 반사되어 방향이 바뀐다.

앞의 두 그림에서 빛은 맞닿은 거울 두 개가 만나는 점에 도달하고, 긴 거울 한 장의 가운데에 부딪힌 것과 똑같이 반사된다. 세 번째 그림에서 빛은 맞닿은 거울 세 개의 꼭짓점에 도달하고, 온 방향 그대로 되돌아간다.

다음 경우에는 빛이 거울 하나 이상의 꼭짓점에 닿지만 튕기지 않고 같은 방향으로 계속 나아간다.

거울의 꼭짓점까지의 거리가 0이 되어도 같은 방향으로 계속 나아가는 데 그 거울을 통과할 필요가 없으면 이렇게 된다. 그래서 빛은 대각선으로 맞닿은 두 거울 사이, 크기가 0인 틈을 지나갈 수 있다. 빛의 크기도 0이라 지나간다.

마지막 경우에는 빛이 거울 하나의 꼭짓점에 닿아 소멸한다.

그 거울이 빛의 진행 경로를 막고 있고, 그 빛은 다른 어떤 거울의 꼭짓점에도 닿지 않았다.

그림 없이 규칙만 적으면 이렇다. 네 칸이 만나는 점에 빛이 도달했다고 하자. 빛이 그대로 나아가면 들어갈 칸을 $F$ , 그 점에 닿는 나머지 두 칸을 $S_1$ , $S_2$ 라고 한다 (네 번째 칸은 빛이 떠나는 칸이다). $F$ 가 빈 공간이면 빛은 방향을 유지한 채 $F$ 로 들어간다. $F$ 가 거울이고 $S_1$ 과 $S_2$ 중 정확히 하나가 거울이면, 두 거울이 이루는 곧은 벽에서 반사된다. $F$ , $S_1$ , $S_2$ 가 모두 거울이면 빛은 왔던 방향으로 되돌아간다. $F$ 가 거울이고 $S_1$ 과 $S_2$ 모두 거울이 아니면 빛은 소멸한다.

빛은 당신에게 닿으면 멈추지만, 당신 칸의 정확한 중심에 닿아야 한다.

자기 모습이 몇 개나 보이는가?

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 각 테스트 케이스의 첫 줄에는 세 정수 $H$ , $W$ , $D$ 가 공백으로 구분되어 주어진다. 이어지는 $H$ 개의 줄에는 각각 $W$ 개의 문자가 주어지고, 이는 그 테스트 케이스의 거울의 방 지도다.

제한

$1 \le T \le 100$
$3 \le H, W \le 30$
$1 \le D \le 50$
지도의 모든 문자는 #, ., X 중 하나다.
각 지도에서 X인 문자는 정확히 하나다.
각 지도의 첫 줄, 마지막 줄, 첫 열, 마지막 열은 모두 #로 채워져 있다.

출력

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 당신에게 보이는 자기 반사상의 개수다.

힌트

첫 번째 예제의 1번 케이스에서는 위, 아래, 왼쪽, 오른쪽 어디를 보아도 빛이 정확히 거리 1을 지난다.

첫 번째 예제의 2번 케이스에서는 오른쪽 위, 왼쪽 위, 오른쪽 아래, 왼쪽 아래를 보면 빛이 거리 1.414...를 지난다. 빛은 당신을 통과하지 못하므로 똑바로 위를 보면 자기 모습이 하나만 보인다.

첫 번째 예제의 5번 케이스에서는 옆에 있는 거울이 빛을 되돌려 보낼 만큼 가깝지만, 그 거울의 꼭짓점에 닿은 빛은 반사되지 않고 소멸한다.

두 번째 예제에서 왼쪽 위를 보면 빛이 대각선으로 맞닿은 두 거울의 꼭짓점 사이를 지나간다. 그 뒤 방의 구석에 닿아 같은 길로 되돌아와 $3\sqrt{2} \approx 4.243$ 만큼 이동해 당신에게 닿으므로, $D = 5$ 일 때는 그 모습이 보이고 $D = 4$ 일 때는 보이지 않는다.