Untitled

// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful. 

#include<iostream>

using namespace std;
#define size 1000000
int queue[size];
int front=-1;
int rear=-1;
int map[105][105];
int N;
int nho;
int lon;
bool visit[105][105];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,1,-1};
bool isEmpty(){
	return front ==rear;
}
void push(int x){
	if(rear==size-1) rear=-1;
	rear++;
	queue[rear]=x;
}
int pop(){
	if(front==size-1) front=-1;
	front++;
	return queue[front];
}
void reset(){
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			visit[i][j]=false;
		}

	}

}
bool bfs(int l , int r){
	front= rear=-1;
	visit[0][0]=true;

	push(0);
	push(0);
	if( map[0][0]<l || map[0][0]>r) return false;
	else{
		while(!isEmpty()){
			int x=pop();
			int y=pop();
			for(int i=0; i<4; i++){
				int x1= x+dx[i];
				int y1= y+dy[i];
				if(x1>=0 && x1<N && y1>=0 && y1<N && !visit[x1][y1] && map[x1][y1]>=l && map[x1][y1]<=r){
					visit[x1][y1]=true;
					push(x1);
					push(y1);
					if(x1==N-1 && y1==N-1){
						return true;
					}

				}

			}


		}
	}
	return false;

}

bool check(int mid){
	for(int i=nho ; i<= lon- mid; i++){
		reset();
		if(bfs(i, i+mid)) return true;
	}
	return false;
}


int tim(int l , int r){
	int mid;
	while(l!=r){
		mid=(l+r)/2;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	return r;
}




int main(int argc, char** argv)
{
	int test_case;
	int T;



	//freopen("text.txt", "r", stdin);
	cin >> T;

	/*
	Read each test case from standard input.
	*/
	for(test_case = 1; test_case <= T; ++test_case)
	{
		lon=0;
		nho=999;
		int ans=0;
		cin>>N;
		for(int i=0; i<N;i++){
			for(int j=0; j<N; j++){
				cin>>map[i][j];
				if(lon<map[i][j]){
					lon=map[i][j];
				}
				if(nho>map[i][j]){
					nho=map[i][j];
				}


			}
		}
		ans=tim(0,lon-nho);

		cout << "#" << test_case << " " <<ans << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}