有一个大小为 $$$n \times n$$$ 的矩阵,由 0 和 1 组成。行从上到下编号为 $$$1$$$ 到 $$$n$$$,列从左到右编号为 $$$1$$$ 到 $$$n$$$。第 $$$x$$$ 行和第 $$$y$$$ 列交叉处的单元格表示为 $$$(x, y)$$$。
AquaMoon 想要将矩阵的所有元素都变为 0。她可以一步执行以下操作:
- 选择任意单元格,设为 $$$(i, j)$$$,然后反转 $$$(i, j)$$$ 中的元素,并反转单元格 $$$(x, y)$$$ 中的所有元素,对于 $$$x > i$$$ 和 $$$x - i \ge \left|y - j\right|$$$。反转一个值意味着将其更改为相反的值:0 变为 1,1 变为 0。
帮助 AquaMoon 确定将矩阵的所有元素变为 0 所需执行的最少步骤数。我们可以证明答案总是存在的。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3000$$$)。
以下 $$$n$$$ 行中的第 $$$i$$$ 包含仅由字符 0 和 1 组成的二进制字符串,长度为 $$$n$$$。
保证所有测试用例的$$$n^2$$$总和不超过$$$9\,000\,000$$$。
输出
对于每个测试用例,打印最小步骤数。
示例
输入 #1
3 5 00100 01110 11111 11111 11111 3 100 110 110 6 010101 111101 011110 000000 111010 001110
输出 #1
1 2 15
注意
在第一个测试用例中,我们可以使用以下方案:
1. 对单元格$$$(1, 3)$$$执行操作。
显然,初始矩阵的元素不全为0,因此至少需要进行一次运算。因此,$$$1$$$ 就是答案。
在第二个测试用例中,我们使用以下方案:
1. 对单元格$$$(3, 3)$$$执行操作;
2. 对单元格$$$(1, 1)$$$执行操作。
可以看出,$$$0$$$或$$$1$$$步中没有办法将所有元素都转换为0,所以答案正是$$$2$$$。