Errich-Tac-Toe (Easy Version)

1000ms

262144K

Description:

The only difference between the easy and hard versions is that tokens of type O do not appear in the input of the easy version.

Errichto gave Monogon the following challenge in order to intimidate him from taking his top contributor spot on Codeforces.

In a Tic-Tac-Toe grid, there are $$$n$$$ rows and $$$n$$$ columns. Each cell of the grid is either empty or contains a token. There are two types of tokens: X and O. If there exist three tokens of the same type consecutive in a row or column, it is a winning configuration. Otherwise, it is a draw configuration.

$\text{[math]}$ The patterns in the first row are winning configurations. The patterns in the second row are draw configurations.

In an operation, you can change an X to an O, or an O to an X. Let $$$k$$$ denote the total number of tokens in the grid. Your task is to make the grid a draw in at most $$$\lfloor \frac{k}{3}\rfloor$$$ (rounding down) operations.

You are not required to minimize the number of operations.

Input:

The first line contains a single integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 300$$$) — the size of the grid.

The following $$$n$$$ lines each contain a string of $$$n$$$ characters, denoting the initial grid. The character in the $$$i$$$-th row and $$$j$$$-th column is '.' if the cell is empty, or it is the type of token in the cell: 'X' or 'O'.

It is guaranteed that not all cells are empty.

In the easy version, the character 'O' does not appear in the input.

The sum of $$$n$$$ across all test cases does not exceed $$$300$$$.

Output:

For each test case, print the state of the grid after applying the operations.

We have proof that a solution always exists. If there are multiple solutions, print any.

Sample Input:

3
3
.X.
XXX
.X.
6
XX.XXX
XXXXXX
XXX.XX
XXXXXX
XX.X.X
XXXXXX
5
XXX.X
.X..X
XXX.X
..X..
..X..

Sample Output:

.X.
XOX
.X.
XX.XXO
XOXXOX
OXX.XX
XOOXXO
XX.X.X
OXXOXX
XOX.X
.X..X
XXO.O
..X..
..X..

Note:

In the first test case, there are initially three 'X' consecutive in the second row and the second column. By changing the middle token to 'O' we make the grid a draw, and we only changed $$$1\le \lfloor 5/3\rfloor$$$ token.

In the second test case, we change only $$$9\le \lfloor 32/3\rfloor$$$ tokens, and there does not exist any three 'X' or 'O' consecutive in a row or column, so it is a draw.

In the third test case, we change only $$$3\le \lfloor 12/3\rfloor$$$ tokens, and the resulting grid is a draw.

Informação

Provedor Codeforces

Código CF1450C1