moutaintest

#include <iostream>
using namespace std;

int n;
int a[105][105];

struct point {
	int r, c;
};

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int visit[105][105];
int min_h, max_h;
bool inside(int x, int y) {
	if (x >= 1 && x <= n && y >= 1 && y <= n) {
		return true;
	}
	return false;
}
int x_next, y_next, ok;
void dfs(int x, int y, int h, int min_h, int max_h) {
	
	if (ok == 1) {
		return;
	}
	if (x == n && y == n) {
		ok = 1;
		return;
	}
	
	
	for (int i = 0 ; i < 4; i++) {
		x_next = x + dx[i];
		y_next = y + dy[i];
		if (inside(x_next, y_next) && visit[x_next][y_next] == 0) {
			int min_tmp = 999999;
			int max_tmp = -1;
			if (a[x_next][y_next] > max_h) {
				max_tmp = a[x_next][y_next];
			}
			else {
				max_tmp = max_h;
			}
			if (a[x_next][y_next] < min_h) {
				min_tmp = a[x_next][y_next];
			}
			else {
				min_tmp = min_h;
			}
			
			if (max_tmp - min_tmp <= h) {
				visit[x][y] = 1;
				//cout << x_next << " " << y_next << " " << min_tmp << " " << max_tmp << endl; 
				dfs(x_next, y_next, h, min_tmp, max_tmp);
				visit[x][y] = 0;
			}
			
		}
	}
}

bool checkk(int h) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visit[i][j] = 0;
		}
	}
	ok = 0;
	visit[1][1] = 1;
	dfs(1, 1, h, a[1][1], a[1][1]);
	if (ok == 1) return true;
	return false;
}

void solve(int testcase) {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}

	int lo = 0;
	int hi = 110;
	int ans = 0;
	
	while (lo < hi) {
		int mid = (lo + hi) / 2;

		if (checkk(mid) == true) {
			//cout << mid << endl;
			ans = mid;
			hi = mid - 1;
		}
		else {
			lo = mid + 1;
		}

	}
	
	
	cout << "#" << testcase << " " << ans << endl;
}

int main() {
	freopen("Text.txt", "r", stdin);
	int t; cin >> t;

	for (int i = 1; i <= t; i++) {
		solve(i);
	}
	return 0;
}