310750: CF1881C. Perfect Square

C. Perfect Squaretime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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.

ExampleInput

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.

题目大意：
克里斯蒂娜有一个 n×n 的矩阵，矩阵由小写拉丁字母填充，其中 n 是偶数。她希望通过更改某些字符使矩阵成为一个完美平方。一个矩阵如果旋转 90 度顺时针一次后保持不变，则称为完美平方。每次操作，克里斯蒂娜可以选择任意单元格，并将其值更改为字母表中下一个字符。如果字符已经是“z”，则其值不变。求使矩阵成为完美平方所需的最小操作次数。

输入输出数据格式：
输入：
- 第一行包含一个整数 t（1≤t≤10^2），表示测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含一个偶数整数 n（2≤n≤10^3），表示矩阵的行数和列数。
- 接下来 n 行，每行包含恰好 n 个小写拉丁字母。
- 保证所有测试用例的 n 之和不超过 10^3。

输出：
- 对于每个测试用例，输出一个数字，表示克里斯蒂娜获得完美平方所需的最小操作次数。

示例：
输入：
```
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
```
输出：
```
1
2
181
5
9
```

注意：
- 第一个测试用例在题目描述中已解释。题目大意： 克里斯蒂娜有一个 n×n 的矩阵，矩阵由小写拉丁字母填充，其中 n 是偶数。她希望通过更改某些字符使矩阵成为一个完美平方。一个矩阵如果旋转 90 度顺时针一次后保持不变，则称为完美平方。每次操作，克里斯蒂娜可以选择任意单元格，并将其值更改为字母表中下一个字符。如果字符已经是“z”，则其值不变。求使矩阵成为完美平方所需的最小操作次数。 输入输出数据格式： 输入： - 第一行包含一个整数 t（1≤t≤10^2），表示测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含一个偶数整数 n（2≤n≤10^3），表示矩阵的行数和列数。 - 接下来 n 行，每行包含恰好 n 个小写拉丁字母。 - 保证所有测试用例的 n 之和不超过 10^3。 输出： - 对于每个测试用例，输出一个数字，表示克里斯蒂娜获得完美平方所需的最小操作次数。 示例： 输入： ``` 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 ``` 输出： ``` 1 2 181 5 9 ``` 注意： - 第一个测试用例在题目描述中已解释。