CF1660E.Matrix and Shifts

You are given a binary matrix $A$ of size $n \times n$. Rows are numbered from top to bottom from $1$ to $n$, columns are numbered from left to right from $1$ to $n$. The element located at the intersection of row $i$ and column $j$ is called $A_{ij}$. Consider a set of $4$ operations:

1. Cyclically shift all rows up. The row with index $i$ will be written in place of the row $i-1$ ($2 \le i \le n$), the row with index $1$ will be written in place of the row $n$.
2. Cyclically shift all rows down. The row with index $i$ will be written in place of the row $i+1$ ($1 \le i \le n - 1$), the row with index $n$ will be written in place of the row $1$.
3. Cyclically shift all columns to the left. The column with index $j$ will be written in place of the column $j-1$ ($2 \le j \le n$), the column with index $1$ will be written in place of the column $n$.
4. Cyclically shift all columns to the right. The column with index $j$ will be written in place of the column $j+1$ ($1 \le j \le n - 1$), the column with index $n$ will be written in place of the column $1$.

The $3 \times 3$ matrix is shown on the left before the $3$-rd operation is applied to it, on the right — after.

You can perform an arbitrary (possibly zero) number of operations on the matrix; the operations can be performed in any order.

After that, you can perform an arbitrary (possibly zero) number of new xor-operations:

• Select any element $A_{ij}$ and assign it with new value $A_{ij} \oplus 1$. In other words, the value of $(A_{ij} + 1) \bmod 2$ will have to be written into element $A_{ij}$.

Each application of this xor-operation costs one burl. Note that the $4$ shift operations — are free. These $4$ operations can only be performed before xor-operations are performed.

Output the minimum number of burles you would have to pay to make the $A$ matrix unitary. A unitary matrix is a matrix with ones on the main diagonal and the rest of its elements are zeros (that is, $A_{ij} = 1$ if $i = j$ and $A_{ij} = 0$ otherwise).

给你一个大小为 $n \times n$ 的二进制矩阵 $A$。行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $n$。位于第 $i$ 行与第 $j$ 列交叉处的元素记为 $A_{ij}$。考虑以下 $4$ 种操作：

1. 将所有行向上循环移位：第 $i$ 行（$2 \le i \le n$）移动至第 $i-1$ 行的位置，第 $1$ 行移动至第 $n$ 行的位置。
2. 将所有行向下循环移位：第 $i$ 行（$1 \le i \le n - 1$）移动至第 $i+1$ 行的位置，第 $n$ 行移动至第 $1$ 行的位置。
3. 将所有列向左循环移位：第 $j$ 列（$2 \le j \le n$）移动至第 $j-1$ 列的位置，第 $1$ 列移动至第 $n$ 列的位置。
4. 将所有列向右循环移位：第 $j$ 列（$1 \le j \le n - 1$）移动至第 $j+1$ 列的位置，第 $n$ 列移动至第 $1$ 列的位置。

左侧显示的是一个 $3 \times 3$ 矩阵在执行第 $3$ 种操作前的状态，右侧为其执行该操作后的状态。

你可以对矩阵执行任意次数（可能为零）的操作；这些操作可以以任意顺序执行。

之后，你可以执行任意次数（可能为零）的新异或操作（xor-operations）：

• 任选一个元素 $A_{ij}$，将其赋值为 $A_{ij} \oplus 1$。换言之，需将 $(A_{ij} + 1) \bmod 2$ 的值写入元素 $A_{ij}$。

每次执行该异或操作花费 $1$ 个 Burl（货币单位）。注意：上述 $4$ 种移位操作是免费的，且只能在异或操作执行之前进行。

输出使矩阵 $A$ 变为单位矩阵所需的最小 Burl 数量。单位矩阵是指主对角线上元素全为 $1$、其余元素全为 $0$ 的矩阵（即当 $i = j$ 时 $A_{ij} = 1$，否则 $A_{ij} = 0$）。

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) —the number of test cases in the test.

The descriptions of the test cases follow. Before each test case, an empty line is written in the input.

The first line of each test case contains a single number $n$ ($1 \le n \le 2000$)

This is followed by $n$ lines, each containing exactly $n$ characters and consisting only of zeros and ones. These lines describe the values in the elements of the matrix.

It is guaranteed that the sum of $n^2$ values over all test cases does not exceed $4 \cdot 10^6$.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

随后是各测试用例的描述。每个测试用例前，输入中均有一空行。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2000$）。

接下来是 $n$ 行，每行恰好包含 $n$ 个字符，且仅由 0 和 1 组成。这些行描述了矩阵中各元素的值。

保证所有测试用例的 $n^2$ 值之和不超过 $4 \cdot 10^6$。

For each test case, output the minimum number of burles you would have to pay to make the $A$ matrix unitary. In other words, print the minimum number of xor-operations it will take after applying cyclic shifts to the matrix for the $A$ matrix to become unitary.

对于每个测试用例，输出使矩阵 $A$ 成为酉矩阵所需支付的 burles 的最小数量。换言之，在对矩阵应用循环移位后，输出使矩阵 $A$ 成为酉矩阵所需的异或操作（xor-operation）的最小次数。

In the first test case, you can do the following: first, shift all the rows down cyclically, then the main diagonal of the matrix will contain only "1". Then it will be necessary to apply xor-operation to the only "1" that is not on the main diagonal.

In the second test case, you can make a unitary matrix by applying the operation $2$ — cyclic shift of rows upward twice to the matrix.

在第一个测试用例中，你可以执行以下操作：首先，将所有行向下循环移位，此时矩阵的主对角线将全部为 "1"；然后，对唯一一个不在主对角线上的 "1" 执行异或（xor）操作。

在第二个测试用例中，你可以对矩阵执行操作 $2$ —— 即将所有行向上循环移位两次，从而得到一个单位矩阵。