Description

To improve her IQ, ZJY started studying combinatorics. One day she solved this problem: given a grid where some cells contain treasure. Each time, starting from the top-left corner, you can only move right or down. What is the minimum number of walks needed so that it is possible to collect all the treasures?

But she was not satisfied and thought of a variation: suppose each cell contains many pieces of treasure, and on each pass through a cell you can take at most one piece of treasure. With other conditions unchanged, what is the minimum number of walks needed so that it is possible to collect all the pieces of treasure?

This time she could not solve it. Can you help her?

Input Format

The first line contains a positive integer $t$, the number of test cases.

For each test case, the first line contains two positive integers $n$ and $m$, indicating the grid has $n$ rows and $m$ columns.

The next $n$ lines each contain $m$ non-negative integers, representing the number of pieces of treasure in that cell ($0$ means no treasure).

Output Format

For each test case, output one integer, the minimum number of walks.

1
3 3
0 1 5
5 0 0
1 0 0

10

Hint

Constraints

For $30\%$ of the testdata, $n \le 5$, $m \le 5$, and the number of pieces of treasure in each cell does not exceed $5$.

For $50\%$ of the testdata, $n \le 100$, $m \le 100$, and the number of pieces of treasure in each cell does not exceed $1000$.

For $100\%$ of the testdata, $1 \le t \le 2$, $1 \le n \le 1000$, $1 \le m \le 1000$, and the number of pieces of treasure in each cell does not exceed $10^6$.

Translated by ChatGPT 5