Capture Surrounded Regions

You are given one or more square grids consisting only of the characters X and O. Your task is to capture all regions that are completely surrounded by X. A region is captured by flipping all O's to X's in that surrounded region.

An O should not be flipped if it is on the border of the grid or if it is connected (horizontally or vertically) to an O on the border. The connectivity is defined in the four cardinal directions (up, down, left, right).

The description of the problem is similar to a flood-fill problem. Use depth-first search (DFS) or other methods to mark the border-connected regions before capturing the surrounded regions.

In summary, for each grid:

• Identify all O's that are connected to the grid border.
• Flip all other O's (those that are completely surrounded by X) to X.
• Restore the temporary markings back to O.

inputFormat

The input is read from standard input (stdin) and consists of multiple test cases. The first line contains an integer T, the number of test cases. For each test case, the first line contains an integer n representing the dimensions of the grid (n x n), followed by n lines each containing a string of length n made up of characters X and O.

Example Input:

1
3
XOX
OXO
XOX

outputFormat

For each test case, output the modified grid to the standard output (stdout). Each grid should be printed row by row. Do not output extra spaces or newlines between rows, except a newline at the end of each row.

Example Output:

XOX
OXO
XOX

## sample

1
3
XOX
OXO
XOX

XOX
OXO
XOX

</p>