Untitled

#include<iostream>
using namespace std;

int T, n;
int arr[105][105], visit[105][105];
int mina, tru, maxa;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int rs;

int rear, front;
struct toado{
	int x, y;
};
toado queue[1000000];
void init() {
	rear = 0;
	front = 0;
}
void push(int x, int y) {
	queue[rear].x = x;
	queue[rear].y = y;
	rear ++;
}
toado pop() {
	toado t = queue[front];
	front ++;
	return t;
}

void nhap() {
	cin >> n;
	mina = 10000000; maxa = 0;
	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < n; j ++) {
			cin >> arr[i][j];
			visit[i][j] = 0;
			if(mina > arr[i][j]) mina = arr[i][j];
			if(arr[i][j] > maxa) maxa = arr[i][j];
		}
	}
	tru = maxa - mina;
}

bool cdk(int x, int y) {
	if(x >= 0 && x < n && y >= 0 && y < n) return true;
	return false;
}

void reset() {
	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < n; j ++) {
			visit[i][j] = 0;
		}
	}
}

void bfs(int minn, int maxx) {
	init();
	push(0,0);
	visit[0][0] = 1;
	while(front < rear) {
		toado t = pop();
		for(int i = 0; i < 4; i ++) {
			int xx = t.x + dx[i];
			int yy = t.y + dy[i];
			if(cdk(xx,yy) && visit[xx][yy] == 0) {
				if(arr[xx][yy] >= minn && arr[xx][yy] <= maxx) {
					visit[xx][yy] = 1;
					push(xx,yy);
				}
			}
		}
		if(visit[n-1][n-1]) break;
	}
}

void bi(int l, int r) {
	if(l == r) {
		rs = l;
		return;
	}
	else {
		int flag = 0;
		int mid = l + (r-l)/2;
		for(int i = mina; i + mid <= maxa; i ++) {
			if(arr[0][0] >= i && arr[0][0] <= i + mid) {
				reset();
				bfs(i,i+mid);
				if(visit[n-1][n-1]) {
					flag = 1;
					break;
				}
			}
		}
		if(flag == 1) bi(l, mid);
		else bi(mid+1, r);
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);

	cin >> T;
	for(int t = 1; t <= T; t ++) {
		rs = 0;
		nhap();
		bi(0, tru);
		cout << "#" << t << " " << rs << endl;
	}
	return 0;
}