No submission language available for this problem.

Background

Special for beginners, ^_^

Description

在一个黑暗的迷宫中，你需要找到通往自由的道路。迷宫由一个 $n \times m$ 的矩阵表示，每个单元格要么是墙壁（用数字 $0$ 表示），要么是通道（用数字 $1$ 表示）。

你发现了一个特殊的技巧，可以帮助你找到更多的通道。这个技巧是选择一个 $2 \times 2$ 的子矩阵，在这个子矩阵中选择一个 L 形，将这个 L 形里的 $3$ 个通道单元格变成墙壁（将数字 $1$ 变成 $0$）。注意，这个 $L$ 形至少含有一个通道单元格。

你想要最大化使用这个技巧的次数，以便找到尽可能多的通道并逃离迷宫。请问你最多可以使用这个技巧多少次？

Format

Input

输入的第一行包含一个整数 $t$ ($1 \leq t \leq 500$) 表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($2 \leq n, m \leq 500$) 表示迷宫的行数和列数。

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

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

Output

对于每个测试用例，输出可以进行的最大操作次数。

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

Limitation

在第一个测试样例中，一种最优的操作顺序如下（红色字体表示进行操作的 $L$ 形图案）：

• 进行任何操作之前的矩阵：

$$\left[ \begin{matrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ \end{matrix} \right] $$

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

$$\left[ \begin{matrix} 1 & \color{red}0 & \color{red}0 \\ 1 & \color{red}0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ \end{matrix} \right] $$

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

$$\left[ \begin{matrix} 1 & 0 & \color{red}0 \\ 1 & \color{red}0 & \color{red}0 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ \end{matrix} \right] $$

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

$$\left[ \begin{matrix} 1 & 0 & 0 \\ 1 & \color{red}0 & \color{red}0 \\ 0 & 1 & \color{red}0 \\ 1 & 1 & 0 \\ \end{matrix} \right] $$

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

$$\left[ \begin{matrix} 1 & 0 & 0 \\ \color{red}0 & \color{red}0 & 0 \\ \color{red}0 & 1 & 0 \\ 1 & 1 & 0 \\ \end{matrix} \right] $$

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

$$\left[ \begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & \color{red}0 \\ 1 & \color{red}0 & \color{red}0 \\ \end{matrix} \right] $$

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

$$\left[ \begin{matrix} 1 & 0 & 0 \\ 0 & \color{red}0 & 0 \\ 0 & \color{red}0 & \color{red}0 \\ 1 & 0 & 0 \\ \end{matrix} \right] $$

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

$$\left[ \begin{matrix} \color{red}0 & \color{red}0 & 0 \\ \color{red}0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \\ \end{matrix} \right] $$

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

$$\left[ \begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ \color{red}0 & 0 & 0 \\ \color{red}0 & \color{red}0 & 0 \\ \end{matrix} \right] $$

在样例中的第三个测试样例中，我们无法执行任何操作，因为矩阵中没有任何 $1$。

在样例中的第四个测试样例中，无论我们在第一次操作中选择哪个 $L$ 形图案，最终都会剩下一个 $1$。因此，我们将执行 $2$ 次操作。

1s, 1024KiB for each test case.