K. Path Planning 2
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 \lt m$$$ or move to its bottom cell $$$(i + 1, j)$$$ if $$$i \lt 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})$$$.

Example
Input
2
2 3
2 0 1
0 3 4
1 5
100 0 2 0 1
Output
1
3
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$$$.