给定一个二进制矩阵 $$$A$$$,大小为 $$$n \times n$$$。行从上到下从 $$$1$$$ 到 $$$n$$$ 编号,列从左到右从 $$$1$$$ 到 $$$n$$$ 编号。位于行 $$$i$$$ 和列 $$$j$$$ 相交处的元素称为 $$$A_{ij}$$$。考虑一组 $$$4$$$ 操作:
1. 循环向上移动所有行。索引为 $$$i$$$ 的行将替换行 $$$i-1$$$ ($$$2 \le i \le n$$$),索引为 $$$1$$$ 的行将替换行 $$$n$$$。
2. 循环下移所有行。索引为 $$$i$$$ 的行将替换行 $$$i+1$$$ ($$$1 \le i \le n - 1$$$),索引为 $$$n$$$ 的行将替换行 $$$1$$$。
3. 循环将所有列向左移动。索引为 $$$j$$$ 的列将代替列 $$$j-1$$$ ($$$2 \le j \le n$$$),索引为 $$$1$$$ 的列将代替列 $$$n$$$。
4. 循环右移所有列。索引为 $$$j$$$ 的列将代替列 $$$j+1$$$ ($$$1 \le j \le n - 1$$$),索引为 $$$n$$$ 的列将代替列 $$$1$$$。
$$$3 \times 3$$$ 矩阵显示在左侧,在对其应用 $$$3$$$-rd 运算之前,右侧显示在应用 $$$3$$$-rd 运算之后。
您可以对矩阵执行任意(可能为零)次数的运算;这些操作可以按任何顺序执行。
之后,您可以执行任意(可能为零)数量的新异或运算:
- 选择任意元素 $$$A_{ij}$$$ 并为其分配新值 $$$A_{ij} \oplus 1$$$。换句话说,$$$(A_{ij} + 1) \bmod 2$$$ 的值必须写入元素$$$A_{ij}$$$。
此异或运算的每次应用都会花费一个树节。请注意,$$$4$$$ 移位操作是免费的。这些 $$$4$$$ 操作只能在执行异或操作之前执行。
输出使 $$$A$$$ 矩阵统一所需的最小节数。酉矩阵是主对角线上有 1 且其余元素为零的矩阵(即,如果 $$$i = j$$$,则 $$$A_{ij} = 1$$$,否则 $$$A_{ij} = 0$$$)。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中的测试用例数量。
测试用例的描述如下。在每个测试用例之前,在输入中写入一个空行。
每个测试用例的第一行包含一个数字 $$$n$$$ ($$$1 \le n \le 2000$$$)
接下来是 $$$n$$$ 行,每行恰好包含 $$$n$$$ 字符,并且仅由零和一组成。这些行描述了矩阵元素中的值。
保证所有测试用例的 $$$n^2$$$ 值之和不超过 $$$4 \cdot 10^6$$$。
输出
对于每个测试用例,输出使 $$$A$$$ 矩阵统一所需的最少 burles 数。换句话说,打印对矩阵应用循环移位以使 $$$A$$$ 矩阵变为酉后所需的最小异或运算数。
示例
输入 #1
4 3 010 011 100 5 00010 00001 10000 01000 00100 2 10 10 4 1111 1011 1111 1111
输出 #1
1 0 2 11
注意
在第一个测试用例中,您可以执行以下操作:首先,将所有行循环下移,然后矩阵的主对角线将仅包含“1”。然后,有必要对不在主对角线上的唯一“1”应用异或运算。
在第二个测试用例中,您可以通过应用操作 $$$2$$$ 来创建酉矩阵 - 将行向上循环移位两次到矩阵。