#include <iostream>

int a[100][100],b[100][100],n,min,max,cdif,sign;

bool walk(int x,int y)//use cdif and sign as parameters ,avoid para-passing .also use min and max as two varibles .
//this fuction is to check if there's a way from [0][0] to [n-1][n-1] and the difference within cdif .
{
	int cmax,cmin;
	cmax=max=(a[x][y]>max)?a[x][y]:max;
	cmin=min=(a[x][y]>min)?min:a[x][y];
	if(max-min>cdif)return false;
	if(x==n-1&&y==n-1)return true;
	b[x][y]=sign;
	if(x>0&&b[x-1][y]!=sign&&walk(x-1,y))return true;
	max=cmax;
	min=cmin;
	if(x<n-1&&b[x+1][y]!=sign&&walk(x+1,y))return true;
	max=cmax;
	min=cmin;
	if(y>0&&b[x][y-1]!=sign&&walk(x,y-1))return true;
	max=cmax;
	min=cmin;
	if(y<n-1&&b[x][y+1]!=sign&&walk(x,y+1))return true;
	--b[x][y];
	return false;
}

void search(int a,int b)
{
	if(a!=b)
	{
		++sign;
		cdif=(a+b)>>1;
		max=0;
		min=200;
		if(walk(0,0))
			search(a,cdif);
		else
			search(++cdif,b);
	}
}

int main(void)
{
	int i,j,k,r,N;

	scanf("%d",&N);
	r=0;
	while(r++<N)
	{
		scanf("%d",&n);
		min=200;
		max=sign=0;
		for(i=0;i<n;++i)
			for(j=0;j<n;++j)
			{
				b[i][j]=0;
				scanf("%d",&a[i][j]);
				min=(a[i][j]<min)?a[i][j]:min;
				max=(a[i][j]<max)?max:a[i][j];
			}
		search(0,max-min);
		printf("Scenario #%d:\n%d\n\n",r,cdif);
	}

	return 0;
}