← 返回题目列表

Codeforces · 1881/C

C. 完美正方形

中文机器翻译题面 查看原题

Kristina 有一个大小为 $$$n$$$ × $$$n$$$ 的矩阵,用小写拉丁字母填充。 $$$n$$$ 的值是偶数。

她想改变一些字符,使她的矩阵变成一个完美的正方形。如果一个矩阵顺时针旋转 $$$90^\circ$$$ 一次后保持不变,则该矩阵称为完全平方矩阵。

下面是将矩阵旋转 $$$90^\circ$$$ 的示例:

在一次操作中,Kristina 可以选择任何单元格并将其值替换为字母表中的下一个字符。如果该字符等于“z”,则其值不会改变。

求使矩阵成为完全平方数所需的最少运算次数。

例如,如果 $$$4$$$ by $$$4$$$ 矩阵如下所示:

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

那么对字母 b 应用 $$$1$$$ 操作就足够了,以粗体突出显示。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^2$$$) — 测试用例的数量。

然后是每个测试用例的描述。

每个测试用例的第一行包含一个偶数 $$$n$$$ ($$$2 \le n \le 10^3$$$) — 矩阵中的行数和列数。

接下来是 $$$n$$$ 行,每行恰好包含 $$$n$$$ 小写拉丁字母。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^3$$$。

输出

对于每个测试用例,在单独的行上输出一个数字:Kristina 获得完美平方所需的最少运算次数。

示例

输入 #1

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

1
2
181
5
9

注意

第一个测试用例在问题陈述中进行了解释。