거울의 방

당신은 2차원 평면에 살고 있고, 즐겨 찾는 장소 중 하나가 거울의 방이다. 거울의 방은 격자로 나뉜 (당연히 2차원인) 방이다. 격자의 각 칸에는 정사각형 거울이 놓여 있거나, 빈 공간이거나, 당신이 서 있다. 당신의 너비와 높이는 0이고, 당신은 자신이 있는 칸의 정확한 중심에 서 있다.

몸집이 아주 작아도, 빛이 정확히 되돌아오면 당신은 자신의 상을 본다. 예를 들어 아래 배치를 보자. #는 칸을 가득 채운 정사각형 거울, .는 빈 공간, 대문자 X는 당신이 그 칸의 중심에 있다는 표시이다.

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

똑바로 위를 보거나 똑바로 오른쪽을 보면 자신의 상이 보인다.

거울의 방에는 안개가 짙어서 D 단위보다 멀리 있는 것은 보이지 않는다. D=3이라고 하자. 위를 보면 상까지의 거리가 1이다 (거울까지 0.5, 되돌아오며 0.5). 오른쪽을 보면 상까지의 거리가 3이고 (거울까지 1.5, 되돌아오며 1.5), 그 상이 보인다. 아래를 보면 상까지의 거리가 5라서 보이지 않는다.

거울의 방에서 빛이 어떻게 나아가는지를 정확히 알아야 한다. 빛은 거울에 닿을 때까지 직선으로 나아간다. 거울의 꼭짓점이 아닌 부분에 닿으면 입사각과 반사각이 같은 보통의 방식으로 반사된다. 반면 빛이 거울의 꼭짓점에 닿는 경우는 더 복잡하다. 아래 그림이 각 경우를 설명한다.

다음 경우에 빛은 꼭짓점에 도달해 반사되고, 진행 방향이 바뀐다:

앞의 두 경우에서 빛은 나란히 붙은 두 거울이 만나는 점에 도달했다. 이때 빛은 하나의 긴 거울 한가운데에 부딪힌 것과 똑같이 반사됐다. 세 번째 경우에서 빛은 나란히 붙은 거울 세 개의 꼭짓점에 도달했고, 왔던 방향 그대로 되돌아갔다.

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

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

마지막 경우에 빛은 거울 하나의 꼭짓점에 도달해 소멸한다:

거울이 빛의 진행 경로 위에 있었고, 그 빛줄기는 다른 어떤 거울의 꼭짓점에도 도달하지 않았다.

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

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

첫 줄에 테스트 케이스의 개수 T가 주어진다. 이어서 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.414...만큼 나아간다. 빛은 당신을 통과하지 못하므로 똑바로 위를 보면 자신의 상이 하나만 보인다.

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