CF1864D.Matrix Cascade

There is a matrix of size $n \times n$ which consists of 0s and 1s. The rows are numbered from $1$ to $n$ from top to bottom, the columns are numbered from $1$ to $n$ from left to right. The cell at the intersection of the $x$-th row and the $y$-th column is denoted as $(x, y)$.

AquaMoon wants to turn all elements of the matrix to 0s. In one step she can perform the following operation:

• Select an arbitrary cell, let it be $(i, j)$, then invert the element in $(i, j)$ and also invert all elements in cells $(x, y)$ for $x \gt i$ and $x - i \ge \left|y - j\right|$. To invert a value means to change it to the opposite: 0 changes to 1, 1 changes to 0.

Help AquaMoon determine the minimum number of steps she need to perform to turn all elements of the matrix to 0s. We can show that an answer always exists.

存在一个大小为 $n \times n$ 的矩阵，其中仅包含 0 和 1。行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $n$。第 $x$ 行与第 $y$ 列相交的单元格记作 $(x, y)$。

AquaMoon 希望将矩阵中所有元素都变为 0。在每一步操作中，她可以执行以下操作：

• 任选一个单元格，记为 $(i, j)$，然后翻转 $(i, j)$ 处的元素，并同时翻转所有满足 $x > i$ 且 $x - i \ge \left|y - j\right|$ 的单元格 $(x, y)$ 中的元素。所谓“翻转”是指将值取反：0 变为 1，1 变为 0。

请帮助 AquaMoon 确定将矩阵所有元素变为 0 所需的最少操作步数。可以证明该问题总有解。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \le n \le 3000$).

The $i$-th of the following $n$ lines contains a binary string only of characters 0 and 1, of length $n$.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $9\,000\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。随后是各测试用例的描述。

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

接下来的 $n$ 行中，第 $i$ 行包含一个长度为 $n$ 的二进制字符串，仅由字符 0 和 1 组成。

保证所有测试用例的 $n^2$ 之和不超过 $9\,000\,000$。

For each test case, print the minimum number of steps.

对于每个测试用例，输出最少步数。

In the first test case, we can use the following scheme:

1. perform the operation on the cell $(1, 3)$.

Clearly, the elements of the initial matrix are not all 0, so at least one operation is required. Thus, $1$ is the answer.

In the second test case, we use the following scheme:

1. perform the operation on the cell $(3, 3)$;
2. perform the operation on the cell $(1, 1)$.

It can be shown that there is no way to convert all elements to 0s in $0$ or $1$ steps, so the answer is exactly $2$.

在第一个测试用例中，我们可以采用以下方案：

1. 对单元格 $(1, 3)$ 执行操作。

显然，初始矩阵的元素并非全为 $0$，因此至少需要一次操作。故答案为 $1$。

在第二个测试用例中，我们采用以下方案：

1. 对单元格 $(3, 3)$ 执行操作；
2. 对单元格 $(1, 1)$ 执行操作。

可以证明，无法在 $0$ 步或 $1$ 步内将所有元素变为 $0$，因此答案恰好为 $2$。