[SNCPC2019] Paper-cutting

剪纸是中国最古老、最受欢迎的民间艺术之一。它在地理上可以分为南方风格和北方风格。以江苏扬州、浙江乐清作品为代表的南方风格，设计巧妙美观，雕刻精美，造型有趣。北方风格以河北蔚县、丰宁为主体，以陕北作品为代表，造型夸张、气势恢宏、刻画生动、图案多样。 基本的裁剪由单个图像组成，还有对称的设计，通常是通过在成比例的折痕上折叠，然后裁成一个形状，当展开时，就形成了对称的设计。中国剪纸通常是对称的。剪纸通常是 $2$、 $4$ 、 $24$ 等偶数系列。 你会得到一张大小为 $n \times m$ 的纸， 它被划分为 $n \times m$ 个大小为 $1 \times 1$ 的块在。这张纸可以按以下方式折叠： - 可以在两列之间选择一条垂直线，也可以在两行之间选择一条水平线。这条线把纸分成两面。 - 你用这条线作为对称轴，把小的一面折到大的一面上。如果纸的两面大小相等，从两边对折。 你想用这张纸做一幅剪纸杰作。首先，使用上述方法将纸张折叠几次（包括零次）。然后你用剪刀剪纸。每次剪切时，都可以从折叠的纸上剪切出一个连接的部分（即使从外面无法接触到该部分并将其扔掉。请注意，如果两个 $ 1\times 1$ 的块共享一条边，则它们是连接的。 纸张的最终外观是一个包含 $0$ 和 $1$ 的大小为 $n \times m$ 的矩阵，你想知道需要使用剪刀时的最小裁剪次数。 ## 输入格式 有多个测试数据。输入的第一行包含一个整数 $T$ ，表示测试数据的数量。对于每个测试数据： 第一行包含两个整数 $n$ 和 $m$ ( $1 \le n \times m \le 10^6$ )表示纸张的大小。 接下来的 $n$ 行中的每一行都包含一个长度为 $m$ 的01字符串，其中 $\texttt{0}$ 表示 $1\times 1$ 块被剪切掉， $\texttt{1}$ 意味着 $1 \times 1$ 块保留在最后的剪纸上。 保证所有测试数据的 $n \times m$ 之和不超过 $10^6$ 。 ## 输出格式 对于每个测试数据输出一行，其中包含一个整数，表示所需的最小裁剪次数。 ## 样例 #1 ### 样例输入 #1 ``` 3 2 5 11001 11001 5 7 1001100 0110011 0101101 0010010 1000000 3 2 11 11 11 ``` ### 样例输出 #1 ``` 1 4 0 ``` ## 提示 对于样例一,你可以通过这种方式将唯一的 $0$ 剪出: $$\begin{array}{ccc|cc} 1&1&0&0&1\\1&1&0&0&1\end{array} \to \begin{array}{ccc} 1&1&0\\ \hline 1&1&0\end{array} \to \begin{array}{ccc} 1&1&0\end{array}$$ 对于样例二，你可以按照以下方式折叠并裁剪出 $0$ 的 $4$ 个连通块： $$\begin{array}{cccc|ccc} 1&0&0&1&1&0&0\\0&1&1&0&0&1&1\\0&1&0&1&1&0&1\\0&0&1&0&0&1&0\\1&0&0&0&0&0&0\end{array} \to \begin{array}{cccc} 1&0&0&1\\0&1&1&0\\0&1&0&1\\0&0&1&0\\1&0&0&0\end{array}$$

Paper-cutting is one of the oldest and most popular folk arts in China. It can be geographically divided into a southern and a northern style. The southern style, represented by works from Yangzhou in Jiangsu Province and Yueqing in Zhejiang Province, features ingenious and beautiful designs, exquisite carving and interesting shapes. The northern style, mainly from Yuxian and Fengning in Hebei Province and best represented by works from northern Shaanxi, features exaggerated shapes, vigorousness, vivid depictions, and diverse patterns. There are basic cut-outs, consisting of a single image, and symmetrical designs, that are usually created by some folding over a proportioned crease, and then cutting a shape, so that when unfolded, it forms a symmetrical design. Chinese paper cuttings are usually symmetrical. The paper cutouts are usually in an even number series of $2$, $4$, $24$, etc. You are given a piece of paper in the shape of a matrix of size $n \times m$. It is partitioned into $n \times m$ blocks of size $1 \times 1$. The piece of paper can be folded in the following way: - You choose a vertical line between two of its columns or a horizontal line between two of its rows. This line splits the paper into two sides. - You use the line as the folding axis and fold the smaller side of the paper onto the larger one going over the axis. If both sides of the paper are of equal size, you may fold from either side. You would like to make a paper-cutting masterpiece from this paper. At first, you fold the paper using the method above several times (including zero times). Then you use scissors to cut the paper. Each time you cut, you can cut out a connected component from the folded paper (even if the component is not reachable from outside) and throw it away. Note that two $1 \times 1$ blocks are connected if they share an edge. Given the final look of the paper, which is a matrix of size $n \times m$ containing $0$s and $1$s, you would like to know the minimum number of cuts needed when using the scissors.

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains two integers $n$ and $m$ ($1 \le n \times m \le 10^6$): the size of the paper. Each of the next $n$ lines contains a binary string of length $m$, where $\texttt{0}$ means the $1 \times 1$ block is cut out and $\texttt{1}$ means the $1 \times 1$ block remains on the final paper-cutting. It is guaranteed that the sum of $n \times m$ over all test cases does not exceed $10^6$.

For each test case output one line containing one integer, indicating the minimum number of cuts needed.

3
2 5
11001
11001
5 7
1001100
0110011
0101101
0010010
1000000
3 2
11
11
11

1
4
0

For the first sample test case, you can fold in the following way and cut the only $0$ out: $$\begin{array}{ccc|cc} 1&1&0&0&1\\1&1&0&0&1\end{array} \to \begin{array}{ccc} 1&1&0\\ \hline 1&1&0\end{array} \to \begin{array}{ccc} 1&1&0\end{array}$$ For the second sample test case, you can fold in the following way and cut the $4$ connected components of $0$s out: $$\begin{array}{cccc|ccc} 1&0&0&1&1&0&0\\0&1&1&0&0&1&1\\0&1&0&1&1&0&1\\0&0&1&0&0&1&0\\1&0&0&0&0&0&0\end{array} \to \begin{array}{cccc} 1&0&0&1\\0&1&1&0\\0&1&0&1\\0&0&1&0\\1&0&0&0\end{array}$$