I. Path Planning
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. Each integer from $$$0$$$ to $$$(n \times m - 1)$$$ (both inclusive) appears exactly once in the grid.

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 maximize $$$\text{mex}(\mathbb{S})$$$ and calculate this maximum possible value.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ 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} \lt n \times m$$$) where $$$a_{i, j}$$$ indicates the integer in cell $$$(i, j)$$$. Each integer from $$$0$$$ to $$$(n \times m - 1)$$$ (both inclusive) appears exactly once in the grid.

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 maximum possible value of $$$\text{mex}(\mathbb{S})$$$.

Example
Input
2
2 3
1 2 4
3 0 5
1 5
1 3 0 4 2
Output
3
5
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} = \{1, 2, 4, 5\}$$$ so $$$\text{mex}(\mathbb{S}) = 0$$$.
  • The second path is $$$(1, 1) \to (1, 2) \to (2, 2) \to (2, 3)$$$. $$$\mathbb{S} = \{1, 2, 0, 5\}$$$ so $$$\text{mex}(\mathbb{S}) = 3$$$.
  • The third path is $$$(1, 1) \to (2, 1) \to (2, 2) \to (2, 3)$$$. $$$\mathbb{S} = \{1, 3, 0, 5\}$$$ so $$$\text{mex}(\mathbb{S}) = 2$$$.

So the answer is $$$3$$$.

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} = \{1, 3, 0, 4, 2\}$$$ so $$$\text{mex}(\mathbb{S}) = 5$$$.