Description

在一个 $n*n$ 的整数矩阵 $grid$ 中，每一个方格的值 $grid[i][j]$ 表示位置 $(i,j)$ 的平台高度。

当开始下雨时，在时间为 $t$ 时，水池中的水位为 $t$。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 $(0,0)$ 出发。输出你到达坐标方格的右下平台 $(n-1,n-1)$ 所需的最少时间。

Input Format

有 $T(0<T<=100)$ 组样例。

第一行输入一个整数 $T$。

每组样例描述如下：

第一行输入一个正整数 $n(1<n<=50)$。

接下来 $n$ 行， 每行 $n$ 个数，描述矩阵 $grid$ ，其中 $0<=grid[i][j]<=10^7$。

Output Format

输出 $T$ 行。

每行输出对应样例的答案，即你到达坐标方格的右下平台 $(n-1,n-1)$ 所需的最少时间。

2
5
0 1 2 3 4
24 23 22 21 5
12 13 14 15 16
11 17 18 19 20
10 9 8 7 6
2
0 2
1 3

16
3

Hint

对于样例 $1$

必须等到时间为 $16$，此时才能保证平台 $(0, 0)$ 和 $(4, 4)$ 是连通的。

Source

1816 Online Judge 10.100.0.232