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

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

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.


-----Examples-----

Input
3
3
.O.
OOO
.O.
6
XXXOOO
XXXOOO
XX..OO
OO..XX
OOOXXX
OOOXXX
5
.OOO.
OXXXO
OXXXO
OXXXO
.OOO.
Output
.O.
OXO
.O.
OXXOOX
XOXOXO
XX..OO
OO..XX
OXOXOX
XOOXXO
.OXO.
OOXXO
XXOXX
OXXOO
.OXO.


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

Difficulty: HARD
Tags: Mathematics

Constructive algorithms

Starter code:

Solutions:
import sys
input = lambda : sys.stdin.readline().rstrip()
T = int(input())
for _ in range(T):
	N = int(input())
	X = [[a for a in input()] for _ in range(N)]
	C = [0] * 3
	D = [0] * 3
	for i in range(N):
		Xi = X[i]
		for j in range(N):
			if Xi[j] == 'X':
				C[(i + j) % 3] += 1
			elif Xi[j] == 'O':
				D[(i + j) % 3] += 1
	(aaa, bbb) = (0, 0)
	f = 0
	for k in range(3):
		for l in range(3):
			if k == l:
				continue
			if C[k] + D[l] <= (sum(C) + sum(D)) // 3:
				for i in range(N):
					Xi = X[i]
					for j in range(N):
						if (i + j) % 3 == k:
							if Xi[j] == 'X':
								Xi[j] = 'O'
								aaa += 1
						elif (i + j) % 3 == l:
							if Xi[j] == 'O':
								Xi[j] = 'X'
								bbb += 1
				f = 1
				break
		if f:
			break
	for x in X:
		print(''.join(x))


for _ in range(int(input())):
	N = int(input())
	X = [[a for a in input()] for _ in range(N)]
	C = [0] * 3
	D = [0] * 3
	(aaa, bbb) = (0, 0)
	f = 0
	for i in range(N):
		Xi = X[i]
		for j in range(N):
			if Xi[j] == 'X':
				C[(i + j) % 3] += 1
			elif Xi[j] == 'O':
				D[(i + j) % 3] += 1
	for k in range(3):
		for l in range(3):
			if k == l:
				continue
			if C[k] + D[l] <= (sum(C) + sum(D)) // 3:
				for i in range(N):
					Xi = X[i]
					for j in range(N):
						if (i + j) % 3 == k:
							if Xi[j] == 'X':
								Xi[j] = 'O'
								aaa += 1
						elif (i + j) % 3 == l:
							if Xi[j] == 'O':
								Xi[j] = 'X'
								bbb += 1
				f = 1
				break
		if f:
			break
	for x in X:
		print(''.join(x))