#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;
}