끝까지 살아남는 발명가

Izabella와 Olga는 번갈아 가며 차례를 진행하는 새로운 게임을 하고 있다. 이 게임에서 두 사람은 테마파크를 위해 일하는 놀이기구 발명가 역할을 맡는다. 게임판은 테마파크의 지도를 나타내는 정사각형 칸의 행렬이다. 일부 칸은 새 놀이기구를 설치하기에 적합한 곳으로 지정되었다.

놀이기구가 설치되면 이를 홍보하는 표지판도 자동으로 설치된다. 각 대각선 방향으로 $4$명의 표지판 설치자가 파견된다. 북동쪽 방향으로 이동하는 설치자는 다음과 같이 행동한다. 놀이기구가 설치된 칸에서 시작하여 현재 칸의 북동쪽 칸을 확인한다. 그곳에 칸이 없거나 그 칸이 이미 점유되어 있으면 멈춘다. 그렇지 않으면 그 칸으로 이동하여 그곳에 표지판을 설치하고 이 과정을 반복한다. 북서쪽, 남동쪽, 남서쪽 방향으로 이동하는 표지판 설치자들도 이동 방향만 다를 뿐 같은 방식으로 행동한다. 놀이기구나 표지판 중 하나가 있는 칸은 점유된 것으로 간주한다.

예를 들어 아래 왼쪽 그림이 지도이고, 노란색 칸이 놀이기구를 설치할 수 있는 장소를 나타낸다고 하자. 지도의 $3,4$에 놀이기구를 설치하면(이제 파란색 정사각형으로 표시됨), 회색으로 표시된 칸에도 표지판이 설치된다. 이전에는 놀이기구를 설치할 수 있었던 일부 장소에는 이제 표지판이 있으므로 더 이상 놀이기구를 설치할 수 없다. 두 번째 놀이기구를 $3,6$에 설치한 뒤에는 새로운 표지판 설치자들이 기존 표지판이 있는 곳까지만 이동하며, 그 결과 오른쪽 그림과 같은 상황이 된다는 점에 유의하라.

자신의 차례에 플레이어는 이용 가능한 어느 장소에든 놀이기구를 설치할 수 있으며, 그 후 표지판 설치자들이 자동으로 행동하여 예제에서처럼 다른 장소들을 이용할 수 없게 만들 수도 있다. 게임의 목표는 상대보다 오래 살아남는 것이다. 자신의 차례에 놀이기구를 설치할 수 있는 장소가 하나도 없는 플레이어가 게임에서 패배한다.

Izabella가 먼저 시작한다. 두 플레이어 모두 게임에서 이기기 위해 최적으로 플레이한다고 할 때, Izabella가 자신의 첫 차례에 선택할 수 있는 서로 다른 수 중 그녀의 승리로 이어지는 것은 몇 개인가?

제한

시간 제한: 40초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i, j$에 대해 $\mathbf{L_{i,j}}$는 대문자 X 또는 마침표(.)이다.

테스트 세트 1 (Visible Verdict)

$1 \le \mathbf{R} \le 10$. $1 \le \mathbf{C} \le 10$. 최대 $10$개의 $i, j$ 조합에 대해 $\mathbf{L_{i,j}} =$ X. (입력 행렬에는 X가 최대 10개 있다.)

테스트 세트 2 (Hidden Verdict)

$1 \le \mathbf{R} \le 100$. $1 \le \mathbf{C} \le 100$. $\mathbf{R} \times \mathbf{C} \le 200$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 게임판의 행 수와 열 수를 각각 나타내는 두 정수 $\mathbf{R}$와 $\mathbf{C}$가 담긴 줄로 시작한다. 그다음 $\mathbf{R}$개의 줄이 주어진다. 이 줄들 중 $i$번째 줄에는 $\mathbf{C}$개의 문자로 이루어진 문자열 $\mathbf{L_{i,1}}\mathbf{L_{i,2}}\cdots\mathbf{L_{i,C}}$가 주어진다. $i$번째 행과 $j$번째 열의 칸이 새 놀이기구를 설치할 수 있는 장소이면 $\mathbf{L_{i,j}}$는 대문자 X이고, 그렇지 않으면 마침표(.)이다.

각 테스트 케이스마다 Case #$x$: $y$을 담은 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$은 Izabella가 게임에서 승리하게 되는 가능한 첫 차례의 수를 나타내는 정수이다.

예제 케이스 #1에서 Izabella가 이길 수 있는 유일한 수는 자신이 발명한 놀이기구를 $(2,4)$에 설치하는 것이다. 다른 $6$개의 수를 두면 두 사람 모두 최적으로 플레이할 경우 Olga가 이길 수 있는 게임이 된다.

예제 케이스 #2에서 Izabella가 둘 수 있는 유효한 첫 수는 어느 것이든 $2$개의 장소가 남은 게임판으로 이어지며, Olga가 남은 $2$개의 장소 중 어느 곳에 두더라도 $1$개의 장소가 남은 게임판으로 이어져 Izabella가 게임에서 이기게 된다. 따라서 $3$개의 유효한 수는 어느 것이든 승리하는 수이다.

예제 케이스 #3에서는 $5$개의 장소 중 가운데 장소에 두는 것만 Izabella가 이기는 수이다. 다른 $4$개의 수를 두면 두 사람 모두 최적으로 플레이할 경우 Olga가 이길 수 있는 게임이 된다.

예제 케이스 #4에서 Izabella가 둘 수 있는 유효한 첫 수는 어느 것이든 Olga에게 유효한 수를 하나도 남기지 않으므로, Izabella는 어느 수를 두어도 즉시 승리한다.