你有一个由 n 行 m 列组成的矩阵。该矩阵的每个单元格包含 0 或 1。

我们将一个缺少一个角单元格的 2x2 正方形区域称为 L 形图案。在一次操作中，你可以选取一个 L 形图案（该图案中至少有一个单元格包含 1），并将其中的所有数字替换为零。

计算对给定矩阵所能进行的最大操作次数。

输入格式

第一行包含一个整数 t (1 ≤ t ≤ 500) - 测试用例的数量。随后是每个测试用例的描述。

每个测试用例的第一行包含两个整数 n 和 m (2 ≤ n, m ≤ 500) - 矩阵的大小。

接下来的 n 行，每行包含一个长度为 m 的二进制字符串 - 表示矩阵的描述。

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

输出格式

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

Samples

4
4 3
101
111
011
110
3 4
1110
0111
0111
2 2
00
00
2 2
11
11

8
9
0
2

第一个测试用例

在第一个测试用例中，一个最优操作序列如下（加粗字体表示执行操作所针对的“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 次操作。

Limitation

1s, 1024KiB for each test case.