Untitled

#include <iostream>
#define N 305
using namespace std;
int n;
int a[N][N];
int sx[N];
int sy[N];
int dd[N][N];
int sv,sl,sc;
int minn,maxx;
int hx[]={0,-1,0,1};
int hy[]={-1,0,1,0};
void doc()
{
	cin>>n;
	minn=200;
	maxx=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			{
				cin>>a[i][j];
				if(a[i][j]>maxx)maxx=a[i][j];
				if(a[i][j]<minn)minn=a[i][j];
		}
		//cout<<minn<<" ---"<<maxx<<"\n";
}
bool kt(int u,int v)
{
	if(a[1][1]>v||a[1][1]<u)return false;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)dd[i][j]=0;
	int dau=1,cuoi=0;
	sx[++cuoi]=1;
	sy[cuoi]=1;
	dd[1][1]=1;
	while(dau<=cuoi)
	{
		
		int x=sx[dau];
		int y=sy[dau];
		//cout<<x<<" "<<y<<"\n";
		dau++;
		for(int i=0;i<4;i++)
		{
			int xx=x+hx[i];
			int yy=y+hy[i];
			if(xx>0&&xx<=n&&yy>0&&yy<=n)
				if(a[xx][yy]>=u&&a[xx][yy]<=v)
					if(dd[xx][yy]==0)
					{
						dd[xx][yy]=1;
						sx[++cuoi]=xx;
						sy[cuoi]=yy;
					}
		}
	}
	//cout<<u<<" "<<v<<" "<<dd[n][n]<<"\n";
	if(dd[n][n]==1)return true;
	return false;

}
bool check(int k)
{
	
	for(int i=minn;i<=maxx-k;i++)
		{
			//cout<<i<<" "<<i+k<<"\n";
			if(kt(i,i+k))
				{
					//cout<<i<<"- "<<i+k<<"\n";
					return true;
			}
	}
	return false;
}


int main()
{
	//freopen("input.txt","r",stdin);
	int TC;
	cin>>TC;
	for(int tc=1;tc<=TC;tc++)
	{
		doc();
		int lo=0,hi=maxx-minn;
		while(lo<hi)
		{
			int mid=(lo+hi)/2;
			if(check(mid))hi=mid;else lo=mid+1;
		}
		cout<<"#"<<tc<<" ";
		cout<<lo<<"\n";
		//cout<<sv<<" "<<sl<<" "<<sc<<"\n";
	}
	return 0;
}