Bacterial Tactics

Becca and Terry are microbiologists and friendly rivals. When they need a break from research, they play a game together. The game is played on a matrix of unit cells with R rows and C columns. At the start, each cell is either empty or contains radioactive material.

On each turn, if there are no empty cells in the matrix, the player to move loses. Otherwise, the player chooses an empty cell and places a bacteria colony there. There are two colony types: H (horizontal) and V (vertical).

• An H colony occupies the cell it is placed in and tries to spread into the cell immediately to the west (if there is one) and the cell immediately to the east (if there is one).
• A V colony occupies the cell it is placed in and tries to spread into the cell immediately to the south (if there is one) and the cell immediately to the north (if there is one).

Each time a colony tries to spread into a cell:

• If the cell contains radioactive material, the colony mutates, and the player who placed it loses.
• If the cell is empty, the colony occupies it, and the spreading rule applies again from that cell.
• If the cell already contains bacteria (of either type), the colony does not spread into it.

Some players may have only moves that cause a mutation, so they are doomed to lose.

Becca makes the first move. The players alternate until one of them loses. If both play optimally, who wins? If Becca wins, how many distinct winning opening moves does she have? Two opening moves are distinct if and only if they use different cells, different colony types, or both.

The first line contains the number of test cases, T. Each test case begins with a line containing two integers R and C, the number of rows and columns. Then follow R lines of C characters each. The j-th character of the i-th line describes the cell in row i, column j. Each character is either . (an empty cell) or # (a cell with radioactive material).

For each test case, output one line in the form Case #x: y, where x is the test case number starting from 1 and y is an integer. If Becca will not win, y is 0. If she will win, y is the number of distinct winning opening moves she can make.

1 ≤ T ≤ 100.

In case 1, Becca cannot place an H colony in the southwest empty cell or a V colony in the northeast empty cell, because each would spread onto a radioactive cell and she would lose. Her only non-losing opening moves are:

1. Place an H colony in the northwest or northeast empty cell. The colony also spreads into the other of those two cells.
2. Place a V colony in the northwest or southwest empty cell. The colony also spreads into the other of those two cells.

If Becca picks strategy 1, Terry can place a V colony in the southwest empty cell. If Becca picks strategy 2, Terry can place an H colony in the northeast empty cell. Either way, Becca has no empty cell on her next turn, so she loses and Terry wins.

In case 2, every opening move by Becca causes a mutation.

In case 3, five of Becca's opening moves cause a mutation, but the other seven win. She can place an H colony in any cell of the second row, or a V colony in any cell of the second column. In either case, the empty cells split into two disconnected groups of 1 or 2 cells each. In each group, only one colony type can be placed, and placing it fills the whole group. Whichever group Terry fills, Becca fills the other, leaving Terry with no move.

In case 4, both of Becca's two distinct opening moves win.

In case 5, Becca has no possible opening move.