{"raw_statement":[{"iden":"statement","content":"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.\n\nLet $(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$.\n\nLet $\\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."},{"iden":"input","content":"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:\n\nThe 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.\n\nFor 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} < 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.\n\nIt's guaranteed that the sum of $n \\times m$ of all test cases will not exceed $10^6$."},{"iden":"output","content":"For each test case output one line containing one integer indicating the maximum possible value of $\\text{mex}(\\mathbb{S})$."},{"iden":"note","content":"For the first sample test case there are $3$ possible paths.\n\n- 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$.\n- 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$.\n- 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$.\n\nSo the answer is $3$.\n\nFor 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$."}],"translated_statement":null,"sample_group":[["2\n2 3\n1 2 4\n3 0 5\n1 5\n1 3 0 4 2","3\n5"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}