#include <algorithm>
#include <iostream>
#include <array>
#include <tuple>
#include <vector>
constexpr int N(5e4+10),K(4),inf(1e9),M(4e5+10),A(6e4);
int a[N][K],n,k,bb[N][K],cc[N][K];
namespace subtask1
{
	int solve()
	{
		int mx(0),mn(inf);
		for(int i(1);i<=n;++i) mx=std::max(mx,a[i][0]),mn=std::min(mn,a[i][0]);
		return mx-mn;
	}
}
// namespace T
// {
// 	struct _z
// 	{
// 		int mx,tg;
// 		bool clr;
// 	}z[(A+10)<<2];
// 	void clear(int u)
// 	{
// 		z[u].mx=0;z[u].tg=0;
// 		z[u].clr=true;
// 	}
// 	void add(int u,int v)
// 	{
// 		z[u].mx+=v;z[u].tg+=v;
// 	}
// 	void pd(int u)
// 	{
// 		if(z[u].clr)
// 		{
// 			clear(u<<1);clear(u<<1|1);z[u].clr=false;
// 		}
// 		if(z[u].tg)
// 		{
// 			add(u<<1,z[u].tg);add(u<<1|1,z[u].tg);z[u].tg=0;
// 		}
// 	}
// 	void pu(int u)
// 	{
// 		z[u].mx=std::max(z[u<<1].mx,z[u<<1|1].mx);
// 	}
// 	void add(int u,int cl,int cr,int ql,int qr,int v)
// 	{
// 		if(cl>=ql && cr<=qr){add(u,v);return;}if(cl!=cr) pd(u);int mid((cl+cr)>>1);
// 		if(ql<=mid) add(u<<1,cl,mid,ql,qr,v);if(qr>mid) add(u<<1|1,mid+1,cr,ql,qr,v);pu(u);
// 	}
// }
namespace T
{
	struct _z
	{
		int tg,mx;
	}z[(A+10)<<2];
	int m;
	void build(int k)
	{
		m=1;
		while(m<(k+2)) m<<=1;
		for(int i(1);i<(m<<1);++i) z[i].tg=z[i].mx=0;
	}
	int mx(int a,int b){return a>b?a:b;}
	void mdf(int l,int r,int v)
	{
		for(l+=m-1,r+=m+1;l^r^1;l>>=1,r>>=1)
		{
			if(l&1^1) z[l^1].tg+=v,z[l^1].mx+=v;
			if(r&1)   z[r^1].tg+=v,z[r^1].mx+=v;
			z[l>>1].mx=mx(z[l].mx,z[l^1].mx)+z[l>>1].tg;
			z[r>>1].mx=mx(z[r].mx,z[r^1].mx)+z[r>>1].tg;
		}
		while(l>1) z[l>>1].mx=mx(z[l].mx,z[l^1].mx)+z[l>>1].tg,(l>>=1);
	}
}
namespace subtask2
{
	int vsum(0);
	struct rect
	{
		int xl,xm,yl,ym,val;
	};
	int calc(rect *rs,int n,int m)
	{
		vsum+=n;
		struct lne
		{
			int x,yl,yr,val;
			bool operator<(const lne & b) const {return x<b.x;}
		};
		static std::vector<std::tuple<int,int,int>> ls[N*K*2];
		for(int i(1);i<=m+1;++i) ls[i].clear();
		// static lne ls[M*2];int lc(0);
		for(int i(1);i<=n;++i)
		{
			// ls[++lc]={rs[i].xl,rs[i].yl,rs[i].ym,rs[i].val};
			// ls[++lc]={rs[i].xm+1,rs[i].yl,rs[i].ym,-rs[i].val};
			ls[rs[i].xl].emplace_back(rs[i].yl,rs[i].ym,rs[i].val);
			ls[rs[i].xm+1].emplace_back(rs[i].yl,rs[i].ym,-rs[i].val);
		}
		// std::sort(ls+1,ls+lc+1);
		// T::clear(1);
		T::build(m);
		int ans(0);
		// for(int i(1),j;i<=lc;i=j)
		// {
		// 	for(j=i;j<=lc && ls[j].x==ls[i].x;++j)
		// 	{
		// 		// T::add(1,1,A,ls[j].yl,ls[j].yr,ls[j].val);
		// 		T::mdf(ls[j].yl,ls[j].yr,ls[j].val);
		// 	}
		// 	ans=std::max(ans,T::z[1].mx);
		// }
		for(int i(1);i<=m;++i)
		{
			for(auto [l,r,v]:ls[i])
			{
				T::mdf(l,r,v);
			}
			ans=std::max(ans,T::z[1].mx);
		}
		return ans;
		// return 0;
	}
	int solve(int col_mx,int col_mn,int row_mx,int row_mn,int bg)
	{
		int l(0),r(bg-1),mid,ans(inf);
		for(int i(0);i<k;++i) l=std::max(l,std::abs(a[col_mx][i]-a[col_mn][i]));
		auto check=[&](int lim)->bool
		{
			static rect vt[M];int vc(0);
			static std::pair<int,int> k3[M];int k3c(0);
			static int uv[M];int uc(0);
			static int mm[A],qid,vis[A];
			++qid;
			for(int i(1);i<=n;++i) for(int t(0);t<4;++t) vis[a[i][t]]=qid,vis[a[i][t]+lim]=qid;
			for(int i(1);i<A;++i) if(vis[i]==qid) mm[i]=++uc;
			// std::sort(uv+1,uv+uc+1);uc=std::unique(uv+1,uv+uc+1)-uv-1;
			auto idx=[&](int k)->int{return mm[k];};
			for(int i(1);i<=n;++i) for(int t(0);t<k;++t) bb[i][t]=idx(a[i][t]),cc[i][t]=idx(a[i][t]+lim);
			for(int i(1);i<=n;++i)
			{
				static rect av[10];int cnt(0);
				for(int j(0);j<k;++j)
				{
					if(a[col_mx][row_mx]-a[i][row_mx]<=lim && a[i][row_mn]-a[col_mn][row_mn]<=lim)
					{
						static std::pair<int,int> rs[2];int c(0);
						for(int t(0);t<k;++t) if(t!=row_mx && t!=row_mn)
						{
							rs[c++]={bb[i][t],cc[i][t]};
						}
						for(int j(c);j<2;++j) rs[j]={1,1};
						av[cnt++]=(rect){rs[0].first,rs[0].second,rs[1].first,rs[1].second,0};
					}
					if(i==col_mn || i==col_mx) break;
					std::rotate(a[i],a[i]+1,a[i]+k);
					std::rotate(bb[i],bb[i]+1,bb[i]+k);
					std::rotate(cc[i],cc[i]+1,cc[i]+k);
				}
				// std::cerr<<cnt<<std::endl;
				if(!cnt) return false;
				if(k==3)
				{
					std::sort(av,av+cnt,[](auto a,auto b){return a.xl<b.xl;});
					for(int j(0),lm(-inf);j<cnt;++j)
					{
						if(lm<av[j].xm)
						{
							k3[++k3c]={std::max(lm+1,av[j].xl),1};
							k3[++k3c]={av[j].xm+1,-1};lm=av[j].xm;
						}
					}
				}
				else if(k==4)
				{
					for(int j(1);j<(1<<cnt);++j)
					{
						int xl(0),xm(inf),yl(0),ym(inf),val((__builtin_popcount(j)&1)?1:-1);
						for(int t(0);t<cnt;++t) if((j>>t)&1) xl=std::max(xl,av[t].xl),xm=std::min(xm,av[t].xm),yl=std::max(yl,av[t].yl),ym=std::min(ym,av[t].ym);
						if(xl<=xm && yl<=ym)
						{
							vt[++vc]=(rect){xl,xm,yl,ym,val};
							// std::cerr<<lim<<" "<<i<<" "<<xl<<" "<<xm<<" "<<yl<<" "<<ym<<" "<<val<<std::endl;
						}
					}
				}
			}
			if(k==2) return true;
			else if(k==3)
			{
				std::sort(k3+1,k3+k3c+1);
				int cur(0);
				// for(int i(1);i<=k3c;++i)
				// {
				// 	std::cerr<<k3[i].first<<","<<k3[i].second<<" ";
				// }
				// std::cerr<<std::endl;
				for(int i(1);i<=k3c;++i)
				{
					cur+=k3[i].second;
					if(cur==n) return true;
				}
				return false;
			}
			else return calc(vt,vc,uc)==n;
			// else return true;
		};
		while(l<=r)
		{
			mid=(l+r)>>1;
			if(check(mid)){ans=mid;r=mid-1;}
			else{l=mid+1;}
		}
		return ans;
	}
	int solve()
	{
		int mx(0),mn(inf);
		std::pair<int,int> mp{0,0},np{0,0};
		for(int i(1);i<=n;++i)
		{
			for(int j(0);j<k;++j)
			{
				if(a[i][j]>mx){mx=a[i][j];mp={i,j};}
				if(a[i][j]<mn){mn=a[i][j];np={i,j};}
			}
		}
		if(mx==mn) return 0;
		int ans(mx-mn);
		// std::cerr<<mx<<" "<<mn<<" "<<mp.first<<" "<<mp.second<<" "<<np.first<<" "<<np.second<<std::endl;
		if(mp.first==np.first)
		{
			ans=std::min(solve(mp.first,mp.first,mp.second,np.second,ans),ans);
		}
		else
		{
			for(int i(0);i<k;++i)
			{
				if((np.second-i+k)%k!=mp.second) ans=std::min(ans,solve(mp.first,np.first,mp.second,(np.second-i+k)%k,ans));
				std::rotate(a[np.first],a[np.first]+1,a[np.first]+k);
			}
		}
		return ans;
	}
}
int main()
{
	std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
	int T;std::cin>>T>>k;int sumn(0);
	while(T--)
	{
		std::cin>>n;sumn+=n;
		for(int i(0);i<k;++i)
		{
			for(int j(1);j<=n;++j) std::cin>>a[j][i];
		}
		if(k==1){std::cout<<subtask1::solve()<<"\n";}
		else{std::cout<<subtask2::solve()<<"\n";}
	}
	// std::cerr<<sumn<<std::endl;
	// std::cerr<<subtask2::vsum<<std::endl;
	return 0;
}