package Mountain_Walking;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Solution {
static int n, res, hmin, hmax;
static int[][] a, visit, value;
static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };
static int[] qx = new int[10000], qy = new int[10000];
static boolean checkOut(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= n)
return false;
return true;
}
static boolean BFS(int mid) {
int L = hmin;
while(L <= hmax-mid) {
int R = L + mid;
if (a[0][0] < L || a[0][0] > R){
L++;
}else{
visit = new int[n][n];
visit[0][0] = 1;
int front = 0, rear = 1;
qx[front] = 0;
qy[front] = 0;
while (front < rear) {
int xt = qx[front], yt = qy[front];
if(xt == n-1 && yt == n-1) return true;
for(int i = 0; i < 4; i++){
int nx = xt + dx[i], ny = yt + dy[i];
if(checkOut(nx, ny) && visit[nx][ny] == 0 && a[nx][ny] >= L && a[nx][ny] <= R){
qx[rear] = nx;
qy[rear] = ny;
rear++;
visit[nx][ny] = 1;
}
}
front++;
}
L++;
}
}
return false;
}
public static void main(String[] args) {
try {
System.setIn(new FileInputStream("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner scanner = new Scanner(System.in);
int test = scanner.nextInt();
for (int t = 1; t <= test; t++) {
n = scanner.nextInt();
a = new int[n][n];
visit = new int[n][n];
hmin = 110;
hmax = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = scanner.nextInt();
hmin = Math.min(hmin, a[i][j]);
hmax = Math.max(hmax, a[i][j]);
}
}
int L = 0, R = hmax - hmin;
while (L <= R) {
int mid = (L + R) / 2;
if (BFS(mid)) {
res = mid;
R = mid - 1;
} else {
L = mid + 1;
}
}
System.out.println("#" + t + " " + res);
}
scanner.close();
}
}