角落

题目描述

给你一个由 $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

样例输入 #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
• 执行一次操作后的矩阵： 100101011110
• 执行两次操作后的矩阵： 100100011110
• 执行三次操作后的矩阵： 100100010110
• 执行四次操作后的矩阵： 100000010110
• 执行五次操作后的矩阵： 100000010100
• 执行六次操作后的矩阵： 100000000100
• 执行七次操作后的矩阵： 000000000100
• 执行八次操作后的矩阵： 000000000000

在样例中的第三个测试用例，我们不能执行任何操作，因为矩阵中没有任何一个。

在样例中的第四个测试用例，无论我们在第一次操作中选择哪个 L 形图形，我们总会剩下一个 1，所以我们将执行 2 次操作。