题目描述

Errichto给了Monogon以下挑战，目的是为了吓阻他在Codeforces上夺取他的顶级贡献者地位。

在一个井字棋网格中，有$n$行和$n$列。网格的每个单元格要么为空，要么包含一个令牌。有两种类型的令牌:X和O。如果一行或一列中存在三个相同类型的连续令牌，那么这是一个获胜的配置。否则，这是一个平局的配置。

在一次操作中，你可以将一个X改变成一个O，或者将一个O改变成一个X。让$k$表示网格中的总令牌数。你的任务是在最多$\lfloor\dfrac{k}{3}\rfloor$(向下取整)次操作内使网格成为一个平局。

题目格式

输入格式

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

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

接下来的$n$行每行包含一个长度为$n$的字符串，表示初始网格。第$i$行和第$j$列的字符是.，如果单元格为空，或者是单元格中的令牌类型:X或O。

保证不是所有单元格都为空。

所有测试用例中的$\sum n\le 300$。

输出格式

对于每个测试用例，打印应用操作后网格的状态。

我们有证据表明总是存在解决方案。如果存在多个解决方案，打印任意一个。

题目样例

3
3
.O.
OOO
.O.
6
XXXOOO
XXXOOO
XX..OO
OO..XX
OOOXXX
OOOXXX
5
.OOO.
OXXXO
OXXXO
OXXXO
.OOO.

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

样例解释

在第一个测试用例中，初始时第二行和第二列分别有三个O连续。通过将中间的令牌改变为X，我们使得网格成为平局，并且只改变了$1\le \lfloor\dfrac{5}{3}\rfloor$个令牌。

在第二个测试用例中，最终网格是平局的。我们只改变了$8\le \lfloor\dfrac{32}{3}\rfloor$个令牌。

在第三个测试用例中，最终网格是平局的。我们只改变了$7\le \lfloor\dfrac{21}{3}\rfloor$个令牌。