Codeforces Round 903 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

implementation

*1200

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Perfect Square

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputKristina has a matrix of size $$$n$$$ by $$$n$$$, filled with lowercase Latin letters. The value of $$$n$$$ is even.

She wants to change some characters so that her matrix becomes a perfect square. A matrix is called a perfect square if it remains unchanged when rotated $$$90^\circ$$$ clockwise once.

Here is an example of rotating a matrix by $$$90^\circ$$$:

In one operation, Kristina can choose any cell and replace its value with the next character in the alphabet. If the character is equal to "z", its value does not change.

Find the minimum number of operations required to make the matrix a perfect square.

For example, if the $$$4$$$ by $$$4$$$ matrix looks like this:

$$$$$$\matrix{ a & b & b & a \cr b & c & \textbf{b} & b \cr b & c & c & b\cr a & b & b & a \cr }$$$$$$

then it is enough to apply $$$1$$$ operation to the letter b, highlighted in bold.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^2$$$) — the number of test cases.

Then follows the description of each test case.

The first line of each test case contains a single even integer $$$n$$$ ($$$2 \le n \le 10^3$$$) — the number of rows and columns in the matrix.

Then follows $$$n$$$ lines, each containing exactly $$$n$$$ lowercase Latin letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^3$$$.

Output

For each test case, output a single number on a separate line: the minimum number of operations required for Kristina to obtain a perfect square.

Example

Input

54abbabcbbbccbabba2abba6codeforcescodeforcescodeforcescodefo4baaaabbabababaab4bbaaabbaaabaabba

Output

1 2 181 5 9

Note

The first test case is explained in the problem statement.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2023 08:44:06 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|