P9646 [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}$$