P1023迢迢寻故人（trail）

【题目背景】

镇内物资已经重新清点完毕，tfbz 却发现真正困难的是把它们运过星尘原野。为了找到能够规划运输的 Ehundategh，他只得独自穿过这片不断变化的原野。

【题目描述】

星尘原野可以看作一个 $n\times m$ 的网格，其中第 $i$ 行第 $j$ 列的区域记为 $[i,j]$，区域中留有一个非负整数 $a_{i,j}$，表示这里残存的星痕编号。

tfbz 从区域 $[1,1]$ 出发，希望最终到达区域 $[n,m]$。当他位于 $[i,j]$ 时，只能移动到 $[i+1,j]$、$[i-1,j]$、$[i,j+1]$、$[i,j-1]$ 中仍位于原野内的一个区域。他可以重复经过同一区域，但任何时刻都不能离开原野。

记 tfbz 在这次寻找中经过的所有区域里的整数所形成的集合为 $S$。定义这条路线的星痕扰动为 $\operatorname{mex}(S)$，即不属于 $S$ 的最小非负整数。

tfbz 希望受到的星痕扰动尽可能小。请你求出从 $[1,1]$ 到达 $[n,m]$ 的所有可行路线中，最小可能的星痕扰动。

【输入格式】

从文件 $\textbf{\textit{trail.in}}$ 中读入数据。

第一行一个整数 $T$，表示测试数据的组数。

对于每组测试数据：

• 第一行两个正整数 $n,m$，表示网格的行数和列数；
• 接下来 $n$ 行，每行 $m$ 个非负整数，第 $i$ 行第 $j$ 个整数为 $a_{i,j}$。

【输出格式】

输出到文件 $\textbf{\textit{trail.out}}$ 中。

对于每组测试数据，输出一行一个整数，表示最小可能的星痕扰动。

【样例 1 输入】

1322 230 040 052 360 1 272 1 083 394 1 2103 5 6117 8 9

【样例 1 输出】

112230

【说明/提示】

【样例 1 解释】

对于第二组测试数据，任意一条可行路线都会经过编号为 $0$ 和 $1$ 的星痕；tfbz 可以选择一条不经过编号为 $2$ 的星痕的路线，因此最小的星痕扰动为 $2$。

【样例 2】

见选手目录下的 $\textbf{\textit{trail/trail2.in}}$ 和 $\textbf{\textit{trail/trail2.ans}}$。

该组样例符合测试点 $1\sim 4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{trail/trail3.in}}$ 和 $\textbf{\textit{trail/trail3.ans}}$。

该组样例符合测试点 $5\sim 8$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{trail/trail4.in}}$ 和 $\textbf{\textit{trail/trail4.ans}}$。

该组样例符合测试点 $9\sim 12$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{trail/trail5.in}}$ 和 $\textbf{\textit{trail/trail5.ans}}$。

该组样例符合测试点 $13\sim 15$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{trail/trail6.in}}$ 和 $\textbf{\textit{trail/trail6.ans}}$。

该组样例符合测试点 $16\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证：$1\leq T\leq 1000$，$1\leq \sum n\leq 2000$，$1\leq \sum m\leq 2000$，$0\leq a_{i,j}\leq 10^9$。

特殊性质 A：保证同一行中的所有数均相等。

特殊性质 B：保证 $\min(n,m)=1$。