Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem A: Away

Problem A: Away

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 32  Solved: 7
[Submit][Status][Web Board]

Description

Given a N*N field, each cell of the field contains a number indicating the safety when you walk through. When you are in cell(i, j), you can go to cell(i+1,j), (i-1, j), (i, j-1) or (i, j+1).But you can not go outside of the field.
Now please find a path from cell (1,1) to (n, n). You should guarantee the smallest safety in the path as largest as possible.

Input

The first line contains one integer T, indicates the total test cases. Each test case starts with an integer N. Next N lines each line contains N numbers x. (1<=N<=1000 , 0 <= x <= 1e9, T = 15)

Output

For each test case output one line contain answer.

Sample Input

2
2
8 9
3 4
3
1 1 2
2 1 1
3 3 1

Sample Output

4
1

HINT

[Submit][Status][Web Board]