CF1720C.Corners

You are given a matrix consisting of $n$ rows and $m$ columns. Each cell of this matrix contains $0$ or $1$.

Let's call a square of size $2 \times 2$ without one corner cell an L-shape figure. In one operation you can take one L-shape figure, with at least one cell containing $1$ and replace all numbers in it with zeroes.

Find the maximum number of operations that you can do with the given matrix.

你被给定一个由 $n$ 行和 $m$ 列组成的矩阵。该矩阵的每个单元格中包含数字 $0$ 或 $1$。

我们将一个大小为 $2 \times 2$、且缺失一个角上单元格的正方形称为 L 形图形。在一次操作中，你可以选取一个 L 形图形（要求其中至少有一个单元格的值为 $1$），并将该 L 形图形内所有数字替换为 $0$。

求对给定矩阵最多可以执行多少次这样的操作。

The first line contains one integer $t$ ($1 \leq t \leq 500$) — the number of test cases. Then follow the descriptions of each test case.

The first line of each test case contains two integers $n$ and $m$ ($2 \leq n, m \leq 500$) — the size of the matrix.

Each of the following $n$ lines contains a binary string of length $m$ — the description of the matrix.

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases does not exceed $1000$.

第一行包含一个整数 $t$（$1 \leq t \leq 500$），表示测试用例的数量。随后是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \leq n, m \leq 500$），表示矩阵的大小。

接下来的 $n$ 行，每行包含一个长度为 $m$ 的二进制字符串，用于描述该矩阵。

保证所有测试用例中 $n$ 的总和以及 $m$ 的总和均不超过 $1000$。

For each test case output the maximum number of operations you can do with the given matrix.

对于每个测试用例，输出在给定矩阵上所能执行的最大操作次数。

In the first testcase one of the optimal sequences of operations is the following (bold font shows l-shape figure on which operation was performed):

• Matrix before any operation was performed:

  1

  0

  1

  1

  1

  1

  0

  1

  1

  1

  1

  0

• Matrix after $1$ operation was performed:

  1

  0

  0

  1

  0

  1

  0

  1

  1

  1

  1

  0

• Matrix after $2$ operations were performed:

  1

  0

  0

  1

  0

  0

  0

  1

  1

  1

  1

  0

• Matrix after $3$ operations were performed:

  1

  0

  0

  1

  0

  0

  0

  1

  0

  1

  1

  0

• Matrix after $4$ operations were performed:

  1

  0

  0

  0

  0

  0

  0

  1

  0

  1

  1

  0

• Matrix after $5$ operations were performed:

  1

  0

  0

  0

  0

  0

  0

  1

  0

  1

  0

  0

• Matrix after $6$ operations were performed:

  1

  0

  0

  0

  0

  0

  0

  0

  0

  1

  0

  0

• Matrix after $7$ operations were performed:

  0

  0

  0

  0

  0

  0

  0

  0

  0

  1

  0

  0

• Matrix after $8$ operations were performed:

  0

  0

  0

  0

  0

  0

  0

  0

  0

  0

  0

  0

In the third testcase from the sample we can not perform any operation because the matrix doesn't contain any ones.

In the fourth testcase it does not matter which L-shape figure we pick in our first operation. We will always be left with single one. So we will perform $2$ operations.

在第一个测试用例中，一种最优的操作序列如下所示（加粗字体表示执行操作的 L 形区域）：

• 初始矩阵（尚未执行任何操作）：

  1

  0

  1

  1

  1

  1

  0

  1

  1

  1

  1

  0

• 执行 $1$ 次操作后的矩阵：

  1

  0

  0

  1

  0

  1

  0

  1

  1

  1

  1

  0

• 执行 $2$ 次操作后的矩阵：

  1

  0

  0

  1

  0

  0

  0

  1

  1

  1

  1

  0

• 执行 $3$ 次操作后的矩阵：

  1

  0

  0

  1

  0

  0

  0

  1

  0

  1

  1

  0

• 执行 $4$ 次操作后的矩阵：

  1

  0

  0

  0

  0

  0

  0

  1

  0

  1

  1

  0

• 执行 $5$ 次操作后的矩阵：

  1

  0

  0

  0

  0

  0

  0

  1

  0

  1

  0

  0

• 执行 $6$ 次操作后的矩阵：

  1

  0

  0

  0

  0

  0

  0

  0

  0

  1

  0

  0

• 执行 $7$ 次操作后的矩阵：

  0

  0

  0

  0

  0

  0

  0

  0

  0

  1

  0

  0

• 执行 $8$ 次操作后的矩阵：

  0

  0

  0

  0

  0

  0

  0

  0

  0

  0

  0

  0

在样例中的第三个测试用例中，我们无法执行任何操作，因为该矩阵不包含任何数字 1。

在第四个测试用例中，第一次操作选择哪一个 L 形区域均无影响；操作后总会剩余一个 1。因此我们将总共执行 $2$ 次操作。