Untitled

import java.util.Scanner;

public class OptimizedMountainWalking {
    static int n;
    static int[][] mountain = new int[100][100];
    static int front, rear;
    static boolean[][] visited = new boolean[100][100];
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {-1, 0, 1, 0};
    static int[] queueX = new int[1000000];
    static int[] queueY = new int[1000000];

    public static void walk(int x, int y, int start, int end) {
        if (mountain[x][y] < start || mountain[x][y] > end) return;
        front = rear = 0;
        queueX[rear] = x;
        queueY[rear] = y;
        rear++;
        while (front < rear) {
            int xx = queueX[front];
            int yy = queueY[front];
            front++;
            for (int i = 0; i < 4; i++) {
                int _x = xx + dx[i];
                int _y = yy + dy[i];
                if (_x >= 0 && _x < n && _y >= 0 && _y < n) {
                    if (!visited[_x][_y]) {
                        if (mountain[_x][_y] >= start && mountain[_x][_y] <= end) {
                            visited[_x][_y] = true;
                            queueX[rear] = _x;
                            queueY[rear] = _y;
                            rear++;
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int test_case;
        int T;

        T = sc.nextInt();

        for (test_case = 1; test_case <= T; ++test_case) {
            n = sc.nextInt();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    mountain[i][j] = sc.nextInt();
                }
            }
            int left = 0, right = 111;
            while (left < right) {
                int mid = (left + right) / 2;
                boolean check = false;
                for (int i = 0; i <= 110; i++) {
                    for (int k = 0; k < n; k++) {
                        for (int j = 0; j < n; j++) {
                            visited[k][j] = false;
                        }
                    }
                    visited[0][0] = true;
                    walk(0, 0, i, i + mid);
                    if (visited[n - 1][n - 1]) {
                        check = true;
                        break;
                    }
                }
                if (check) right = mid;
                else left = mid + 1;
            }

            System.out.println("#" + test_case + " " + left);
        }
    }
}