C. Perfect Square
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Kristina 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
5
4
abba
bcbb
bccb
abba
2
ab
ba
6
codefo
rcesco
deforc
escode
forces
codefo
4
baaa
abba
baba
baab
4
bbaa
abba
aaba
abba
Output
1
2
181
5
9
Note

The first test case is explained in the problem statement.