Problem C
Path Planning 2

There is a grid with $n$ rows and $m$ columns. Each cell of the grid has an integer in it, where $a_{i, j}$ indicates the integer in the cell located at the $i$-th row and the $j$-th column.

Let $(i, j)$ be the cell located at the $i$-th row and the $j$-th column. You now start from $(1, 1)$ and need to reach $(n, m)$. When you are in cell $(i, j)$, you can either move to its right cell $(i, j + 1)$ if $j < m$ or move to its bottom cell $(i + 1, j)$ if $i < n$.

Let $\mathbb {S}$ be the set consisting of integers in each cell on your path, including $a_{1, 1}$ and $a_{n, m}$. Let $\text{mex}(\mathbb {S})$ be the smallest non-negative integer which does not belong to $\mathbb {S}$. Find a path to minimize $\text{mex}(\mathbb {S})$ and calculate this minimum possible value.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$) indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^6$, $1 \le n \times m \le 10^6$) indicating the number of rows and columns of the grid.

For the following $n$ lines, the $i$-th line contains $m$ integers $a_{i, 1}, a_{i, 2}, \cdots , a_{i, m}$ ($0 \le a_{i, j} \le 10^9$) where $a_{i, j}$ indicates the integer in cell $(i, j)$.

It’s guaranteed that the sum of $n \times m$ of all test cases will not exceed $10^6$.

Output

For each test case output one line containing one integer indicating the minimum possible value of $\text{mex}(\mathbb {S})$.

Note

For the first sample test case there are $3$ possible paths.

• The first path is $(1, 1) \to (1, 2) \to (1, 3) \to (2, 3)$. $\mathbb {S} = \{ 2, 0, 1, 4\} $ so $\text{mex}(\mathbb {S}) = 3$.

• The second path is $(1, 1) \to (1, 2) \to (2, 2) \to (2, 3)$. $\mathbb {S} = \{ 2, 0, 3, 4\} $ so $\text{mex}(\mathbb {S}) = 1$.

• The third path is $(1, 1) \to (2, 1) \to (2, 2) \to (2, 3)$. $\mathbb {S} = \{ 2, 0, 3, 4\} $ so $\text{mex}(\mathbb {S}) = 1$.

So the answer is $\min (3, 1, 1) = 1$.

For the second sample test case there is only $1$ possible path, which is $(1, 1) \to (1, 2) \to (1, 3) \to (1, 4) \to (1, 5)$. $\mathbb {S} = \{ 100, 0, 2, 1\} $ so $\text{mex}(\mathbb {S}) = 3$.

2
2 3
2 0 1
0 3 4
1 5
100 0 2 0 1

1
3