310644: CF1864D. Matrix Cascade

D. Matrix Cascadetime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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 > 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.

Input

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$.

Output

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

ExampleInput

3
5
00100
01110
11111
11111
11111
3
100
110
110
6
010101
111101
011110
000000
111010
001110

Output

1
2
15

Note

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$.

题目大意：
有一个 n x n 的矩阵，由 0 和 1 组成。矩阵的行从上到下编号为 1 到 n，列从左到右编号为 1 到 n。交叉于第 x 行和第 y 列的单元格表示为 (x, y)。

AquaMoon 想要将矩阵的所有元素变为 0。在一步操作中，她可以执行以下操作：
- 选择任意一个单元格，设为 (i, j)，然后翻转 (i, j) 单元格的元素，并且翻转所有满足 x > i 且 x - i ≥ |y - j| 的单元格 (x, y) 中的元素。翻转一个值意味着将其变为相反的值：0 变为 1，1 变为 0。

帮助 AquaMoon 确定她需要执行的最小步数，以便将矩阵的所有元素变为 0。题目保证存在答案。

输入输出数据格式：
输入：
- 第一行包含一个整数 t (1 ≤ t ≤ 10^5)，表示测试用例的数量。
- 每个测试用例的第一行包含一个整数 n (2 ≤ n ≤ 3000)。
- 接下来的 n 行，每行包含一个长度为 n 的只由字符 0 和 1 组成的二进制字符串。

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

输出：
- 对于每个测试用例，输出将其所有元素变为 0 所需的最小步数。

示例输入输出：
输入：
```
3
5
00100
01110
11111
11111
11111
3
100
110
110
6
010101
111101
011110
000000
111010
001110
```
输出：
```
1
2
15
```题目大意： 有一个 n x n 的矩阵，由 0 和 1 组成。矩阵的行从上到下编号为 1 到 n，列从左到右编号为 1 到 n。交叉于第 x 行和第 y 列的单元格表示为 (x, y)。 AquaMoon 想要将矩阵的所有元素变为 0。在一步操作中，她可以执行以下操作： - 选择任意一个单元格，设为 (i, j)，然后翻转 (i, j) 单元格的元素，并且翻转所有满足 x > i 且 x - i ≥ |y - j| 的单元格 (x, y) 中的元素。翻转一个值意味着将其变为相反的值：0 变为 1，1 变为 0。 帮助 AquaMoon 确定她需要执行的最小步数，以便将矩阵的所有元素变为 0。题目保证存在答案。 输入输出数据格式： 输入： - 第一行包含一个整数 t (1 ≤ t ≤ 10^5)，表示测试用例的数量。 - 每个测试用例的第一行包含一个整数 n (2 ≤ n ≤ 3000)。 - 接下来的 n 行，每行包含一个长度为 n 的只由字符 0 和 1 组成的二进制字符串。 保证所有测试用例的 n^2 之和不超过 9,000,000。 输出： - 对于每个测试用例，输出将其所有元素变为 0 所需的最小步数。 示例输入输出： 输入： ``` 3 5 00100 01110 11111 11111 11111 3 100 110 110 6 010101 111101 011110 000000 111010 001110 ``` 输出： ``` 1 2 15 ```