The hot new toy for this year is called "X Squared". It consists of a square by grid of tiles, where is odd. Exactly of the tiles are labeled with an X
, and the rest are blank (which we will represent with the .
character). In each move of the game, the player can either choose and exchange two rows of tiles, or choose and exchange two columns of tiles. The goal of the game is to get all of the X
tiles to be on the two main diagonals of the grid, forming a larger X shape, as in the following example for :
X...X
.X.X.
..X..
.X.X.
X...X
You are about to play with your X Squared toy, which is not yet in the goal state. You suspect that your devious younger sibling might have moved some of the tiles around in a way that has broken the game. Given the current configuration of the grid, can you determine whether it is possible to win or not?
Input Specification
The first line of the input gives the number of test cases, . test cases follow. Each one begins with one line with an integer , the size of the grid. more lines with characters each follow; the character on the of these lines is X
if the tile in the row and column of the grid has an X, or .
if that tile is blank.
Output Specification
For each test case, output one line containing Case #x: y
, where x
is the test case number (starting from ) and y
is POSSIBLE
if it is possible to win, and IMPOSSIBLE
otherwise.
Limits
( is odd.)
The grid has exactly X
tiles and exactly .
tiles.
The grid is not already in the goal state, as described in the problem statement.
Subtask 1 [9/23]
Subtask 2 [14/23]
Sample Input
2
3
..X
XX.
XX.
3
...
XXX
XX.
Sample Output
Case #1: POSSIBLE
Case #2: IMPOSSIBLE
In Sample Case #1, one winning strategy is:
- Swap the top row with the middle row.
- Swap the rightmost column with the middle column.
..X XX. X.X
XX. -> ..X -> .X.
XX. XX. X.X
In Sample Case #2, no sequence of moves can turn the grid into the desired final configuration.
Comments