剪纸是中国最古老、最受欢迎的民间艺术之一。它在地理上可分为南派和北派。南派以江苏扬州和浙江乐清的作品为代表，特点是设计巧妙优美、雕刻精细、造型生动。北派主要来自河北蔚县和丰宁，以陕北的作品为代表，特点是造型夸张、粗犷有力、描绘生动、图案多样。

剪纸有基本剪纸，由单幅图像组成；也有对称设计，通常通过在比例折痕上折叠，然后剪出一个形状，展开后形成对称设计。中国剪纸通常是对称的。剪纸作品通常呈偶数系列，如 2, 4, 24 等。

你得到一张 $n \times m$ 大小的纸。它被划分为 $n \times m$ 个 $1 \times 1$ 的方块。纸张可以按以下方式折叠：

1. 你选择两列之间的一条垂直线或两行之间的一条水平线。这条线将纸张分成两部分。
2. 你以该线为折叠轴，将较小的一侧折叠到较大的一侧上。如果两侧大小相等，你可以从任意一侧折叠。

你想用这张纸制作一件剪纸杰作。首先，你按照上述方法折叠纸张若干次（包括零次）。然后，你用剪刀剪纸。每次剪裁时，你可以从折叠后的纸张中剪出一个连通分量（即使该分量从外部不可达）并将其丢弃。注意，如果两个 $1 \times 1$ 的方块共享一条边，则它们是连通的。

给定纸张的最终外观，即一个包含 0 和 1 的 $n \times m$ 矩阵，你想知道使用剪刀所需的最少剪裁次数。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \times m \le 10^6$)：纸张的大小。

接下来的 $n$ 行，每行包含一个长度为 $m$ 的二进制字符串，其中 “0” 表示该 $1 \times 1$ 方块被剪掉，“1” 表示该 $1 \times 1$ 方块保留在最终的剪纸作品上。

保证所有测试数据的 $n \times m$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示所需的最少剪裁次数。

样例

样例输入 1

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

样例输出 1

1
4
0

说明

对于第一个样例测试数据，你可以按以下方式折叠并剪掉唯一的 0：

$$ \begin{matrix} 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 \end{matrix} \to \begin{matrix} 1 & 1 & 0 \\ 1 & 1 & 0 \end{matrix} \to 1 \ 1 \ 0 $$

对于第二个样例测试数据，你可以按以下方式折叠并剪掉 4 个 0 的连通分量：

$$ \begin{matrix} 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{matrix} \to \begin{matrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{matrix} $$