Errich-Tac-Toe (Hard Version)
Contest: Codeforces Global Round 12
Difficulty rating: 2300
Tags: constructive algorithms, math

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.

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 format:
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.

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

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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

In the second test case, the final grid is a draw. We only changed $$$8\le \lfloor 32/3\rfloor$$$ tokens.

In the third test case, the final grid is a draw. We only changed $$$7\le \lfloor 21/3\rfloor$$$ tokens.

Example input:
3
3
.O.
OOO
.O.
6
XXXOOO
XXXOOO
XX..OO
OO..XX
OOOXXX
OOOXXX
5
.OOO.
OXXXO
OXXXO
OXXXO
.OOO.

Example output:
.O.
OXO
.O.
OXXOOX
XOXOXO
XX..OO
OO..XX
OXOXOX
XOOXXO
.OXO.
OOXXO
XXOXX
OXXOO
.OXO.

Editorial:
If for every three consecutive tokens in the grid, we make sure there is an X and there is an O, we are done. For each cell $$$(i,j)$$$, let's associate it with the color $$$(i+j)\bmod 3$$$. Since every three consecutive cells contains one of each color, if we make all of one color X and all of a different color O, it would be a solution. It remains to prove that one such way makes at most $$$\lfloor \frac{k}{3}\rfloor$$$ operations.
For each token on the grid, it is associated with a color ($$$0$$$, $$$1$$$, or $$$2$$$) and a type (X or O). Therefore each token falls into one of $$$6$$$ categories. So we can make a table for how many tokens fall in each category.
Firstly, $$$k=x_0+x_1+x_2+o_0+o_1+o_2$$$.
Let $$$a_{ij}$$$ denote the number of operations we make if we flip all X's in cells with color $$$i$$$ and flip all O's in cells with color $$$j$$$. Then $$$a_{ij}=x_i+o_j$$$.
Now, we have $$$a_{01}+a_{02}+a_{10}+a_{12}+a_{20}+a_{21}=2k$$$.
Finally, $$$\min\{a_{01},a_{02},a_{10},a_{12},a_{20},a_{21}\}\le \lfloor 2k/6\rfloor=\lfloor \frac{k}{3}\rfloor$$$.
Here's the coloring in an example. We flip all green X's and blue O's.