Untitled

public class S {

	static int[][] map;
	static int maxh = 0;
	static int[][] v;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();

		for (int tc = 1; tc <= T; tc++) {
			maxh = 0;

			int n = sc.nextInt();
			map = new int[n][n];

			for (int i = 0; i < map.length; i++) {
				for (int j = 0; j < map.length; j++) {
					map[i][j] = sc.nextInt();
					maxh = Math.max(maxh, map[i][j]);
				}
			}

			int high = maxh;
			int low = 0;
			while (low < high) {
				int mid = (low + high) / 2;
				if (check_mid(mid)) {
					high = mid;
				} else {
					low = mid + 1;
				}
			}

			System.out.println("#" + tc + " " + high);

			map = null;
		}
	}

	private static boolean check_mid(int mid) throws Exception {
		for (int i = 0; i + mid <= maxh; i++) {
			v = new int[map.length][map.length];
			if (bfs(i, i + mid)) {
				return true;
			}
			v = null;
		}
		return false;
	}

	private static boolean bfs(int low, int high) throws Exception {
		if (map[0][0] > high || map[0][0] < low)
			return false;

		Queue<NodeCs> qt = new Queue<NodeCs>();
		qt.enQueue(new NodeCs(0, 0));
		while (!qt.isEmpty()) {
			NodeCs tmpN = qt.peek();
			qt.deQueue();
			if (v[tmpN.i][tmpN.j] == 0) {
				v[tmpN.i][tmpN.j] = 1;
				for (int i = 0; i < 4; i++) {
					int nI = tmpN.i + dx[i];
					int nJ = tmpN.j + dy[i];
					if (checkBound(nI, nJ)) {
						if (map[nI][nJ] >= low) {
							if (map[nI][nJ] <= high) {
								if (nI == map.length - 1 && nJ == map.length - 1)
									return true;
								if (v[nI][nJ] == 0)
									qt.enQueue(new NodeCs(nI, nJ));
							}
						}
					}
				}
			}
		}
		qt = null;
		return false;
	}

	private static boolean checkBound(int nI, int nJ) {
		return (nI >= 0 && nI < map.length && nJ >= 0 && nJ < map.length);
	}

	static class Queue<T> {
		int front, rear;
		int MAX_SIZE = 100000;
		T[] arr;

		public Queue() {
			front = rear = -1;
			arr = (T[]) new Object[MAX_SIZE];
		}

		boolean isEmpty() {
			return front == -1;
		}

		T peek() {
			return arr[front];
		}

		void enQueue(T x) {
			if (front == -1) {
				front = 0;
			}
			arr[++rear] = x;
		}

		void deQueue() throws Exception {
			if (isEmpty()) {
				throw new Exception("Queue is empty");
			}
			if (front >= rear) {
				front = rear = -1;
			} else {
				front++;
			}
		}

		int getSize() {
			return rear - front;
		}
	}

	static class NodeCs {
		int i, j;

		public NodeCs(int i, int j) {
			this.i = i;
			this.j = j;
		}
	}
}