CF1611G.Robot and Candies

Polycarp has a rectangular field of $n \times m$ cells (the size of the $n \cdot m$ field does not exceed $10^6$ cells, $m \ge 2$), in each cell of which there can be candy. There are $n$ rows and $m$ columns in the field.

Let's denote a cell with coordinates $x$ vertically and $y$ horizontally by $(x, y)$. Then the top-left cell will be denoted as $(1, 1)$, and the bottom-right cell will be denoted as $(n, m)$.

If there is candy in the cell, then the cell is marked with the symbol '1', otherwise — with the symbol '0'.

Polycarp made a Robot that can collect candy. The Robot can move from $(x, y)$ either to $(x+1, y+1)$, or to $(x+1, y-1)$. If the Robot is in a cell that contains candy, it takes it.

While there is at least one candy on the field, the following procedure is executed:

• Polycarp puts the Robot in an arbitrary cell on the topmost row of the field. He himself chooses in which cell to place the Robot. It is allowed to put the Robot in the same cell multiple times.
• The Robot moves across the field and collects candies. He controls the Robot.
• When the Robot leaves the field, Polycarp takes it. If there are still candies left, Polycarp repeats the procedure.

Find the minimum number of times Polycarp needs to put the Robot on the topmost row of the field in order to collect all the candies. It is guaranteed that Polycarp can always collect all the candies.

Polycarp 有一块大小为 $n \times m$ 的矩形田地（田地总单元格数 $n \cdot m$ 不超过 $10^6$，且满足 $m \ge 2$），每个单元格中可能有糖果。田地共有 $n$ 行和 $m$ 列。

我们用坐标 $(x, y)$ 表示一个单元格，其中 $x$ 表示从上往下的行号，$y$ 表示从左往右的列号。因此，左上角单元格记为 $(1, 1)$，右下角单元格记为 $(n, m)$。

若某单元格中有糖果，则该单元格标记为字符 '1'；否则标记为 '0'。

Polycarp 制作了一个可收集糖果的机器人。该机器人可以从当前单元格 $(x, y)$ 移动到 $(x+1, y+1)$ 或 $(x+1, y-1)$。当机器人位于含有糖果的单元格时，它会取走该糖果。

只要田地上至少还剩一颗糖果，就重复执行以下过程：

• Polycarp 将机器人放置在田地最上方一行（即第 $1$ 行）的任意一个单元格中；具体放置在哪一列由 Polycarp 自主决定。允许多次将机器人放在同一单元格中。
• 机器人在田地上移动并收集糖果；其移动路径由 Polycarp 控制。
• 当机器人移出田地边界时，Polycarp 将其收回。若此时仍有糖果剩余，则 Polycarp 重复上述过程。

求 Polycarp 为收集全部糖果，最少需要将机器人放置在最上方一行的次数。题目保证 Polycarp 总能收集完所有糖果。

The first line of input data contains an integer $t$ ($1 \le t \le 10^4$) — the number of input data sets in the test.

Before each input data, there is a blank line in the test. Next is a line that contains integers $n$ and $m$ ($2 \le m$, $2 \le n \cdot m \le 10^6$) — field sizes. This is followed by $n$ lines, $i$-th of which describes the $i$-th line of the field. Each of them is a string of size $m$ characters: the symbol '1' corresponds to a cell with candy, the symbol '0' — an empty cell.

It is guaranteed that the sum of $n \cdot m$ values for all input data sets in the test does not exceed $10^6$.

输入数据的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试中输入数据组的数量。

每组输入数据前均有一空行。接下来是一行，包含两个整数 $n$ 和 $m$（$2 \le m$，$2 \le n \cdot m \le 10^6$），表示场地的尺寸。随后是 $n$ 行，其中第 $i$ 行描述场地的第 $i$ 行。每行是一个长度为 $m$ 的字符串：字符 '1' 表示该格子中有一颗糖果，字符 '0' 表示该格子为空。

保证测试中所有输入数据组的 $n \cdot m$ 值之和不超过 $10^6$。

Print $t$ lines, each line should contain the answer to the corresponding set of input data: the minimum number of times Polycarpus needs to put the Robot on the topmost row of the field in order to collect all the candies.

输出 $t$ 行，每行应包含对应组输入数据的答案：即 Polycarpus 为收集所有糖果，至少需要将机器人放置在场地最顶行的次数。

In the first set Polycarp may not put the Robot on the field at all, so the answer "0"

In the second set, Polycarp will need to place the robot on the field twice. The Robot can collect candies like this: for the first time Polycarp puts the Robot in the cell $(1, 1)$ and collects candies at the positions $(1, 1)$ and $(3, 3)$. The second time Polycarp can again put the Robot in $(1, 1)$, and then the Robot will move first to $(2,2)$, then to $(3, 1)$ and collect the last candy.

In the fourth set, you can show that the Robot cannot collect all the candies in three passes.

在第一组测试数据中，Polycarp 可以完全不在棋盘上放置机器人，因此答案为 “0”。

在第二组测试数据中，Polycarp 需要将机器人放置到棋盘上两次。机器人收集糖果的方式如下：第一次，Polycarp 将机器人放在格子 $(1, 1)$，从而收集位于 $(1, 1)$ 和 $(3, 3)$ 的糖果；第二次，Polycarp 可再次将机器人放在 $(1, 1)$，随后机器人将先移动至 $(2,2)$，再移动至 $(3, 1)$，从而收集最后一颗糖果。

在第四组测试数据中，可以证明：机器人无法在三次遍历内收集全部糖果。