CF1450C2.Errich-Tac-Toe (Hard Version)

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.

简单版本与困难版本的唯一区别在于：简单版本的输入中不会出现类型为 O 的棋子。

为了震慑 Monogon 不要抢走自己在 Codeforces 上的“顶级贡献者”头衔，Errichto 给了他如下挑战：

在一个井字棋（Tic-Tac-Toe）网格中，共有 $n$ 行和 $n$ 列。网格中的每个格子要么为空，要么包含一个棋子。棋子分为两种类型：X 和 O。若某一行或某一列中存在连续三个同类型的棋子，则该局面为获胜局面；否则，该局面为平局局面。

第一行中的模式均为获胜局面；第二行中的模式均为平局局面。

一次操作定义为将一个 X 改为 O，或将一个 O 改为 X。设 $k$ 表示网格中棋子的总数。你的任务是：至多使用 $\lfloor \frac{k}{3}\rfloor$（向下取整）次操作，使整个网格变为平局局面。

你无需最小化操作次数。

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$.

第一行包含一个整数 $t$（$1\le t\le 100$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1\le n\le 300$）—— 网格的大小。

接下来的 $n$ 行，每行包含一个长度为 $n$ 的字符串，表示初始网格。第 $i$ 行第 $j$ 列的字符为 '.' 表示该格子为空；否则为该格子中棋子的类型：'X' 或 'O'。

保证并非所有格子均为空。

所有测试用例的 $n$ 值之和不超过 $300$。

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.

对每个测试用例，输出执行所有操作后网格的状态。

我们已证明解一定存在。若存在多个解，输出任意一个即可。

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.

在第一个测试用例中，初始时第二行第二列位置存在三个连续的 'O'。通过将中间的字符更改为 'X'，我们使网格变为平局，且仅更改了 $1\le \lfloor 5/3\rfloor$ 个字符。

在第二个测试用例中，最终网格为平局。我们仅更改了 $8\le \lfloor 32/3\rfloor$ 个字符。

在第三个测试用例中，最终网格为平局。我们仅更改了 $7\le \lfloor 21/3\rfloor$ 个字符。