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
注意
第一个测试用例在问题陈述中进行了解释。