给定一个由 $$$n$$$ 行和 $$$m$$$ 列组成的矩阵。该矩阵的每个单元格包含 $$$0$$$ 或 $$$1$$$。
我们将一个大小为 $$$2 \times 2$$$ 且没有角单元的正方形称为 L 形图形。在一项操作中,您可以获取一个 L 形图形,其中至少一个单元格包含 $$$1$$$,并将其中的所有数字替换为零。
找出可以对给定矩阵执行的最大运算次数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 500$$$) — 测试用例的数量。然后遵循每个测试用例的描述。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n, m \leq 500$$$) — 矩阵的大小。
以下 $$$n$$$ 行中的每一行都包含长度为 $$$m$$$ 的二进制字符串 — 矩阵的描述。
保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和不超过 $$$1000$$$。
输出
对于每个测试用例,输出可以对给定矩阵执行的最大操作数。
示例
输入 #1
4 4 3 101 111 011 110 3 4 1110 0111 0111 2 2 00 00 2 2 11 11
输出 #1
8 9 0 2
注意
在第一个测试用例中,最佳操作顺序之一如下(粗体字体显示执行操作的 L 形图形):
- 执行任何操作之前的矩阵:101111011110
- 执行 $$$1$$$ 操作后的矩阵:100101011110
- 执行 $$$2$$$ 操作后的矩阵:100100011110
- 执行 $$$3$$$ 操作后的矩阵:100100010110
- 执行 $$$4$$$ 操作后的矩阵:100000010110
- 执行 $$$5$$$ 操作后的矩阵:100000010100
- 执行 $$$6$$$ 操作后的矩阵:100000000100
- 执行 $$$7$$$ 操作后的矩阵:000000000100
- 执行 $$$8$$$ 操作后的矩阵:000000000000
在示例的第三个测试用例中,我们无法执行任何操作,因为矩阵不包含任何操作。
在第四个测试用例中,我们在第一次操作中选择哪个 L 形图形并不重要。我们将永远只剩下一个。因此我们将执行 $$$2$$$ 操作。