Page not loading? Try clicking here.
Placeholder

#10420

Inventor Outlasting 40s 1024MB

Problems

Izabella and Olga are playing a new game alternating turns. In this game, they personify attraction inventors working for a theme park. The board is a matrix of square cells that illustrates the map of the theme park. Some cells were deemed apt to host a new attraction.

When an attraction is built, signs to advertise it are added automatically. 4 sign builders are sent in each diagonal direction. The one moving towards the north-east direction proceeds as follows: starting at the cell where the location is built, check the cell north-east from its current cell. If there is no cell there, or the cell is occupied, they stop. Otherwise, they move to that cell, build a sign there, and repeat. Sign builders that move in the north-western, south-eastern and south-western directions proceed the same, except for the direction of the movements. A cell is considered occupied if it contains either an attraction or a sign.

For example, suppose the left picture below represents a map, with yellow cells representing the spots where attractions can be built. After an attraction is built on 3,4 of the map (now marked with a blue square), signs are also built on cells marked in gray. Some spots that were previously available for attractions are no longer available because they contain a sign now. Notice after a second attraction is built on 3,6, the new sign builders only move as far as a previous sign, leading to the situation illustrated in the right picture.

Three boards representing the original state and the states after bulding 1 and 2 attractions.

In a turn, a player can choose to build an attraction in any available spot, and then the sign builders proceed automatically, possibly invalidating other spots as in the example. The goal of the game is to outlast the opponent: the player that, in her turn, does not have any available spot to build an attraction loses the game.

Izabella plays first. Assuming both players play optimally to win the game, can you count how many different plays on Izabella's first turn would result in her winning?


Input

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


Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is an integer representing the number of possible first turn plays that result in Izabella winning the game.


Example 

4
5 7
.......
...X.X.
...X.X.
..XX...
..X....
1 5
X.X.X
2 5
X.X.X
.X.X.
2 2
X.
.X
Case #1: 1
Case #2: 3
Case #3: 1
Case #4: 2
In Sample Case #1, the only winning move for Izabella is to put her invented attraction at (2,4). The other 6 moves lead to a game Olga can win if they both play optimally. In Sample Case #2, either of the valid first plays for Izabella leads to a board with 2 remaining spots, and either of the 2 remaining spot for Olga leads to a board with 1 remaining spot which is Izabella's winning game. So any of the 3 valid plays is winning. In Sample Case #3, only playing in the middle one among 5 spots is a winning move for Izabella. The other 4 moves lead to a game Olga can win if they both play optimally. In Sample Case #4, either of the valid first plays for Izabella leaves no valid play for Olga, so Izabella wins immediately with any of them.

Source

GCJ 2022iow D

You must sign in to write code.