#include <bits/stdc++.h>
using namespace std;
const int NR=2e5+5;
int fn=0,maxdd=0;
namespace zhouyoyo{
const int inf=1e9+7;
int g,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,as[NR],ans;
std::string str;
#define F(i,a,b) for(int i=a;i<=b;i++) 
#define D(i,a,b) for(int i=a;i>=b;i--)
#define R(a) std::cin>>a;
#define P(a) std::cout<<a<<' ';
#define Si(a) scanf("%d",&a);
#define Sl(a) scanf("%d",&a); 
#define N std::cout<<'\n';
#define W(p,o) while(p>o) 
#define Tmin(x,y) x=std::min(x,y);
#define Tmax(x,y) x=std::max(x,y);
};
using namespace zhouyoyo;
int maxn,minn,mid,de[NR],a[NR][5];
struct lin{
	int l,r,x,val;
}fer[5000005];
bool cmplin(lin a,lin b){
	if(a.x!=b.x)return a.x<b.x;
	return a.val<b.val;
}
vector<int> vec;
void Getm(){
	maxn=0,minn=inf;
	F(i,1,n) 
		F(j,1,k){
			Tmax(maxn,a[i][j]) 
			Tmin(minn,a[i][j])
		}
}
#define Clear(a) memset(a,0,sizeof(a)) 
void Init(bool flag){
	if(flag)Clear(de); vec.clear();
}
void Tea(){
	F(i,minn,maxn) de[i]+=de[i-1];
}
void TeaUpd(int x,int y,int val){
	if(x>y) return;
	de[x]+=val; de[y+1]-=val;
}
bool IsCover(int x,int y,int u,int v){
	return max(x,u)<=min(y,v);
}
void kis1(){
	P(maxn-minn)N
}
int else3(int x){
	return x==1?2:x-1;
}
void kis2(){
	F(i,1,n){
		if(a[i][1]<a[i][2]) swap(a[i][1],a[i][2]);
	} 
	int ans=0;
	F(j,1,2){
		maxn=0,minn=inf;
		F(i,1,n){
			Tmax(maxn,a[i][j]) 
			Tmin(minn,a[i][j])
		} 
		ans=max(ans,maxn-minn);
	}
	P(ans)N
}
bool check3(int len,bool flag){
	Init(1);
	int L1=maxn-len,R1=maxn;
	int R2=minn+len,L2=minn;
	F(i,1,n){
		int r[4]={},ol=0;
		F(j,1,3) {
			F(p,1,3){
				if(j==p)continue;
				int h=6-j-p;
				if(j!=2&&h<p) continue;
				if(j==2&&h>p)continue;
				int P=p;
				if(flag)swap(h,P);
				if(a[i][h]>=L2&&a[i][h]<=R2&&L1<=a[i][P]&&a[i][P]<=R1){
					if(r[j]==0)ol++; 
					r[j]=a[i][j]; 
				} 
			}
		}
		if(ol<=2){
			F(j,1,3){
				if(r[j]){
					TeaUpd(r[j],r[j]+len,1);
				}
			}
		} if(ol==2){
			F(j,1,3)F(k,j+1,3){
				if(r[j]&&r[k]){
					int l=max(r[j],r[k]),R=min(r[j],r[k])+len;
					if(l<=R) TeaUpd(l,R,-1);
				}
			}
		} if(ol==3){
			TeaUpd(min(r[1],min(r[3],r[2])),maxn,1);
		}
	} 
	Tea();
	F(i,minn,maxn) {
		if(de[i]==n){
			 return 1;
		 }
	}
	return 0;
}
void kis3(){
	l=0,r=maxn-minn;
	W(r,l){
		mid=(l+r)>>1;
		if(check3(mid,0)||check3(mid,1)) r=mid;
		else l=mid+1;
	}
	P(l)N
}
void cross2D(int x,int y,int u,int v,int len){
	const int rx=x+len,ry=y+len,ru=u+len,rv=v+len;
	int a1=max(x,u),a2=min(rx,ru),a3=max(y,v),a4=min(ry,rv);
	if(a1<=a2&&a3<=a4){
		fer[++fn]=(lin){a3,a4,a1,-1}; fer[++fn]=(lin){a3,a4,a2+1,1};
	}
}
void cross2D3(int x,int y,int u,int v,int s,int t,int len){
	const int rx=x+len,ry=y+len,ru=u+len,rv=v+len,rs=s+len,rt=t+len;
	int a1=max(x,max(s,u)),a2=min(rx,min(rs,ru)),a3=max(y,max(t,v)),a4=min(ry,min(rt,rv));
	if(a1<=a2&&a3<=a4){
		fer[++fn]=(lin){a3,a4,a1,1}; fer[++fn]=(lin){a3,a4,a2+1,-1};
	}
}
void cross2D4(int x,int y,int u,int v,int s,int t,int a,int b,int len){
	const int rx=x+len,ry=y+len,ru=u+len,rv=v+len,rs=s+len,rt=t+len,ra=a+len,rb=b+len;
	int a1=max(max(a,x),max(s,u)),a2=min(min(ra,rx),min(rs,ru)),a3=max(max(b,y),max(t,v)),a4=min(min(rb,ry),min(rt,rv));
	if(a1<=a2&&a3<=a4){
		fer[++fn]=(lin){a3,a4,a1,-1}; fer[++fn]=(lin){a3,a4,a2+1,1};
	}
}
int tr[NR<<2],ba[NR<<2],tp=0;

void psd(int p){
	vec.push_back(p<<1); vec.push_back(p<<1|1);
	ba[p<<1]+=ba[p]; ba[p<<1|1]+=ba[p];
	tr[p<<1]+=ba[p]; tr[p<<1|1]+=ba[p];
	ba[p]=0;
}
void upd(int l,int r,int s,int t,int p,int val){
	vec.push_back(p);
	if(l<=s&&t<=r){
		tr[p]+=val; ba[p]+=val; return ;
	} 
	if(ba[p]) psd(p);
	int mid=(s+t)>>1;
	if(l<=mid) upd(l,r,s,mid,p<<1,val);
	if(r>mid) upd(l,r,mid+1,t,p<<1|1,val);
	tr[p]=max(tr[p<<1],tr[p<<1|1]);
}
int qry(int l,int r,int s,int t,int p){
	if(s>r||t<l)return 0;
	if(l<=s&&t<=r){
		return tr[p];
	}
	if(ba[p]) psd(p);
	int mid=(s+t)>>1;
	return qry(l,r,s,mid,p<<1)+qry(l,r,mid+1,t,p<<1|1);
}
bool check4(int len,int flag){
	Init(0); tp=0;
	//Clear(tr); Clear(ba);
	fn=0;
	int L1=maxn-len,R1=maxn;
	int R2=minn+len,L2=minn;
	F(i,1,n){
		int Rx[10]={},Ry[10]={},ol=0;
		F(j,1,4) {
			F(p,1,4){
				F(k,1,4){
				if(j==p||p==k||j==k)continue;
				int h=10-j-p-k;
				if(k-j!=1&&j-k!=3) continue;
				if(h<p&&j!=2) continue;
                if(j==2&&h>p)continue;
				int P=p,K=k,J=j;
				if(flag==1)swap(P,J);
				if(flag==2) swap(P,K);
				if(a[i][h]>=L2&&a[i][h]<=R2&&L1<=a[i][P]&&a[i][P]<=R1){
						Rx[++ol]=a[i][J];
						Ry[ol]=a[i][K];
					} 
				}
			}
		}
			//cout<<ol<<'\n';
		F(i,1,ol){
			fer[++fn]=(lin){Ry[i],Ry[i]+len,Rx[i],1};
			fer[++fn]=(lin){Ry[i],Ry[i]+len,Rx[i]+len+1,-1};
		}
		if(ol>=2){
			F(i,1,ol){
				F(j,i+1,ol){
					cross2D(Rx[i],Ry[i],Rx[j],Ry[j],len);
				}
			}
		} if(ol>=3){
			F(i,1,ol){
				F(j,i+1,ol){
					F(k,j+1,ol){
						cross2D3(Rx[i],Ry[i],Rx[j],Ry[j],Rx[k],Ry[k],len);
					}
				}
			}
		} if(ol==4){
			cross2D4(Rx[1],Ry[1],Rx[2],Ry[2],Rx[3],Ry[3],Rx[4],Ry[4],len);
		}
	}
	//cout<<fn<<'\n';
	sort(fer+1,fer+fn+1,cmplin);
	F(i,1,fn){
		upd(fer[i].l,fer[i].r,1,60000,1,fer[i].val);
		//cout<<qry(19903,19903,1,maxn<<1,1)<<'\n';
			maxdd=max(maxdd,tp);
		if(tr[1]==n) {
			for(int j:vec) tr[j]=ba[j]=0;
			return true;
		}
	}
	for(int j:vec) tr[j]=ba[j]=0;
	return false;
}
void kis4(){
	l=0,r=maxn-minn;
	W(r,l){
		mid=(l+r)>>1;
		if(check4(mid,0)||check4(mid,1)||check4(mid,2)) r=mid;
		else l=mid+1;
	}
	P(l)N
}
void work(){
	R(n) 
	F(j,1,k)
		F(i,1,n)
			R(a[i][j])
	Getm();
	if(k==1) kis1();
	if(k==2) kis2();
	if(k==3) kis3();
	if(k==4) kis4(); 
}
int main(){
	int T;
	R(T) R(k)
	while(T--)
		work();
	return 0;
}