발명가 버티기

Izabella와 Olga는 번갈아 가며 새로운 게임을 합니다. 이 게임에서 두 사람은 놀이공원에서 일하는 놀이기구 발명가 역할을 맡습니다. 게임판은 놀이공원 지도를 나타내는 정사각형 칸들의 행렬입니다. 일부 칸은 새 놀이기구를 세우기에 알맞습니다.

놀이기구가 세워지면 이를 광고하는 표지판이 자동으로 추가됩니다. 대각선 네 방향으로 표지판 설치원 4명이 파견됩니다. 북동쪽으로 가는 설치원은 다음과 같이 움직입니다. 놀이기구를 세운 칸에서 출발해 현재 칸의 북동쪽 칸을 확인합니다. 그 칸이 없거나 이미 차 있으면 멈춥니다. 그렇지 않으면 그 칸으로 이동해 표지판을 세우고 같은 과정을 반복합니다. 북서쪽, 남동쪽, 남서쪽으로 가는 설치원도 진행 방향만 다를 뿐 같은 방식으로 움직입니다. 칸에 놀이기구나 표지판이 있으면 그 칸은 차 있는 것으로 봅니다.

예를 들어 아래 왼쪽 그림은 지도를 보여 주며, 노란색 칸은 놀이기구를 세울 수 있는 자리입니다. $3,4$에 놀이기구를 세우면(파란색 정사각형으로 표시) 회색 칸에 표지판이 세워집니다. 놀이기구를 세울 수 있었던 자리 중 일부는 표지판이 생겨서 더 이상 쓸 수 없게 됩니다. 이후 $3,6$에 두 번째 놀이기구를 세우면 새 설치원은 기존 표지판까지만 진행하여 오른쪽 그림의 상황이 됩니다.

한 턴에 플레이어는 사용 가능한 칸 중 아무 곳에나 놀이기구를 세울 수 있습니다. 그러면 표지판 설치원이 자동으로 움직이며, 예시처럼 다른 칸들이 사용할 수 없게 될 수 있습니다. 게임의 목표는 상대보다 오래 버티는 것입니다. 자기 턴에 놀이기구를 세울 칸이 없는 플레이어가 집니다.

Izabella가 먼저 시작합니다. 두 사람이 이기기 위해 최선을 다한다고 할 때, Izabella가 첫 턴에 할 수 있는 서로 다른 수 중 그녀가 이기게 되는 경우의 수를 구하십시오.

입력의 첫 줄에는 테스트 케이스의 수 $T$가 주어집니다. 이어서 $T$개의 테스트 케이스가 나옵니다. 각 테스트 케이스는 게임판의 행 수와 열 수를 나타내는 두 정수 $R$과 $C$가 적힌 줄로 시작합니다. 그다음 $R$개의 줄이 나옵니다. 그중 $i$번째 줄에는 $C$개의 문자로 이루어진 문자열 $L_{i,1}L_{i,2}\cdots L_{i,C}$가 있습니다. $L_{i,j}$는 $i$행 $j$열 칸이 새 놀이기구를 세울 수 있는 자리이면 대문자 X이고, 아니면 마침표(.)입니다.

각 테스트 케이스에 대해 Case #x: y 형식으로 한 줄을 출력합니다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 Izabella가 첫 턴에 두어 게임에서 이기게 되는 수의 개수입니다.

• $1≤T≤100$.
• 모든 $i,j$에 대해 $L_{i,j}$는 대문자 X 또는 마침표(.)입니다.

예제 1번에서 Izabella가 이기는 유일한 수는 $(2,4)$에 놀이기구를 세우는 것입니다. 나머지 $6$개의 수는 두 사람이 최선을 다할 때 Olga가 이기는 게임으로 이어집니다.

예제 2번에서 Izabella가 둘 수 있는 두 유효한 첫 수는 모두 남은 자리가 $2$개인 판으로 이어집니다. Olga가 둘 수 있는 남은 $2$개의 자리 중 어느 쪽을 골라도 남은 자리가 $1$개인 판이 되며, 이는 Izabella가 이기는 상황입니다. 따라서 유효한 첫 수 $3$개는 모두 이깁니다.

예제 3번에서는 $5$개 자리 중 가운데 자리에 두는 수만 Izabella가 이기는 첫 수입니다. 나머지 $4$개의 수는 Olga가 이기는 게임으로 이어집니다.

예제 4번에서는 Izabella가 둘 수 있는 두 유효한 첫 수 모두 Olga에게 유효한 수를 남기지 않으므로, Izabella는 어느 쪽을 두든 바로 이깁니다.