#include<iostream>
using namespace std;
int map[101][101];
int visited[101][101];
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int n,low,high;
int dfs(int l,int a,int b)
{
	int i,k,t,oldl=low,oldh=high;
	if(map[a][b]<high-l||map[a][b]>low+l)
		return 0;
	if(map[a][b]>high)
		high=map[a][b];
	if(map[a][b]<low)
		low=map[a][b];
	if(a==n&&b==n)
		return 1;
	visited[a][b]=1;
	for(i=0;i<4;i++)
	{
		k=a+dir[i][0];
		t=b+dir[i][1];
		if(k>=1&&k<=n&&t>=1&&t<=n&&!visited[k][t]&&dfs(l,k,t))
			return 1;
	}
	low=oldl;
	high=oldh;
	visited[a][b]=0;
	return 0;
}
int bin_search(int l,int r)
{
	int i,j,k,mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		memset(visited,0,sizeof(visited));
		low=high=map[1][1];
		if(dfs(mid,1,1))
			r=mid;
		else
			l=mid+1;
	}
	return l;
}
int main()
{
	int i,j,k,t=0,num;
	scanf("%d",&num);
	while(num--)
	{
		t++;
		scanf("%d",&n);
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				scanf("%d",&map[i][j]);
		k=bin_search(0,200);
		printf("Scenario #%d:\n%d\n",t,k);
	}
	return 0;
}