Inventor Outlasting

Izabella and Olga take turns playing a new game. In this game, they play attraction inventors working for a theme park. The board is a matrix of square cells that shows the map of the theme park. Some cells are suitable for a new attraction.

When an attraction is built, signs advertising it are added automatically. Four sign builders are sent out, one in each diagonal direction. The builder moving north-east works as follows: starting from the cell where the attraction is built, check the cell north-east of the current cell. If there is no such cell, or the cell is occupied, the builder stops. Otherwise, the builder moves to that cell, builds a sign there, and repeats the process. The builders moving north-west, south-east, and south-west work the same way, only in their own directions. A cell is occupied if it contains either an attraction or a sign.

For example, the left picture below shows a map, where yellow cells are spots where attractions can be built. After an attraction is built at $3,4$ (marked with a blue square), signs are built on the cells marked in gray. Some spots that were available for attractions are no longer available because they now contain a sign. After a second attraction is built at $3,6$, its new sign builders only go as far as an existing sign, which leads to the situation in the right picture.

On a turn, a player can build an attraction on any available spot. The sign builders then proceed automatically, which may make other spots unavailable, as in the example. The goal is to outlast the opponent. The player who has no available spot to build an attraction on their turn loses.

Izabella plays first. Assuming both players play optimally to win, count how many different first moves for Izabella would let her win.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line containing two integers $R$ and $C$, the number of rows and columns of the board. Then $R$ lines follow. The $i$-th of these lines contains a string of $C$ characters $L_{i,1}L_{i,2}\cdots L_{i,C}$. $L_{i,j}$ is an uppercase X if the cell in row $i$ and column $j$ is a spot available for a new attraction, and a period (.) if it is not.

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the number of first moves for Izabella that result in her winning the game.

• $1 \le T \le 100$.
• $L_{i,j}$ is either an uppercase X or a period (.), for all $i,j$.

In Sample Case #1, the only winning move for Izabella is to place her attraction at $(2,4)$. The other $6$ moves lead to a game that Olga wins if both players play optimally.

In Sample Case #2, either valid first move for Izabella leaves a board with $2$ remaining spots. Either of the $2$ remaining spots Olga can then choose leaves a board with $1$ remaining spot, which is a winning position for Izabella. So all $3$ valid first moves win.

In Sample Case #3, only the middle of the $5$ spots is a winning first move for Izabella. The other $4$ moves lead to a game that Olga can win.

In Sample Case #4, either valid first move leaves Olga with no valid move, so Izabella wins immediately with any of them.