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.

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)

For each test case output one line contain answer.