#CF1881C. 完美方阵

完美方阵

CF1881C Perfect Square

题目描述

\hspace{15pt}Kristina 有一个大小为 n×nn \times n 的矩阵,里面填满了小写拉丁字母。nn 的值是偶数。

\hspace{15pt}她想要改变一些字符,使得她的矩阵变成一个完美方阵。一个矩阵被称为完美方阵,如果它在顺时针旋转 9090 度后仍然保持不变。

\hspace{15pt}这是一个顺时针旋转矩阵 9090 度的例子:

\hspace{15pt}在一次操作中,Kristina 可以选择任意一个单元格,并将其值替换为字母表中的下一个字符。如果字符等于 ‘z’\texttt{`z'},则它的值不会改变。

\hspace{15pt}找出使得矩阵成为完美方阵所需的最小操作次数。

\hspace{15pt}例如,如果 4×44 \times 4 的矩阵如下所示:

$\begin{matrix} a & b & b & a \\ b & c & \textbf{b} & b \\ b & c & c & b \\ a & b & b & a \end{matrix}$

\hspace{15pt}那么只需要对加粗的字母 ‘b’\texttt{`b'} 进行 11 次操作即可。

输入格式

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 t(1≦t≦100)t \left(1 \leqq t \leqq 100\right) 代表数据组数,每组测试数据描述如下:

\hspace{15pt}第一行输入一个偶数 n(2≦n≦103)n \left(2 \leqq n \leqq 10^3\right) 代表矩阵的行数和列数。

\hspace{15pt}此后 nn 行,第 ii 行输入一个长度为 nn、仅由小写拉丁字母构成的字符串 sis_i,代表矩阵第 ii 行的内容。

\hspace{15pt}除此之外,保证单个测试文件中所有测试数据的 nn 之和不超过 10310^3。

输出格式

\hspace{15pt}对于每一组测试数据,新起一行,输出一个整数,代表 Kristina 获得完美方阵所需的最小操作次数。

测试样例

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

样例 1 解释

\hspace{15pt}第一个测试用例在题目描述中已经解释过了。