// 那就是希望。
// 即便需要取模，也是光明。

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
struct Seg{
    Seg*L,*R;uint len,tag,v;
    Seg(uint n):L(NULL),R(NULL),len(n),tag(0),v(0){if(n>1)L=new Seg(n>>1),R=new Seg(n-(n>>1));}
    voi clear(){tag=v=0;if(len>1)L->clear(),R->clear();}
    voi add(uint l,uint r,uint w){
        if(l>=r)return;
        if(!l&&r==len){tag+=w,v+=w;return;}
        if(l<(len>>1))
            if(r<=(len>>1))L->add(l,r,w);
            else L->add(l,len>>1,w),R->add(0,r-(len>>1),w);
        else R->add(l-(len>>1),r-(len>>1),w);
        v=std::max(L->v,R->v)+tag;
    }
};
uint A[50005][4],T[200005],Back[200005],n,k;
uint solve3(uint u){
    auto check=[&](uint v)
    {
        static bol Gone[200005];
        static uint Cnt[50005];
        for(uint i=0;i<n*k;i++)Gone[i]=0;
        for(uint i=0;i<n;i++)Cnt[i]=0;
        for(uint i=0;i<n;i++)for(uint j=0;j<k;j++)
            if(T[A[i][j]]-T[0]<=v&&T[n*k-1]-T[A[i][(u+j)%k]]<=v)
                Gone[A[i][((u^3)+j)%k]]=1;
        for(uint i=0,j=0,cnt=0;i<n*k;i++)if(Gone[i]){
            while(T[i]-T[j]>v){
                if(Gone[j]&&!--Cnt[Back[j]])cnt--;
                j++;
            }
            if(!Cnt[Back[i]]++)cnt++;
            if(cnt==n)return true;
        }
        return false;
    };
    uint l=0,r=T[n*k-1]-T[0];
    while(l<r){uint mid=(l+r)>>1;if(check(mid))r=mid;else l=mid+1;}
    return l;
}
uint solve4(uint u){
    Seg S(n*k);
    auto check=[&](uint v)
    {
        S.clear();
        static bol Gone[200005];
        static uint L[200005];
        static std::vector<std::pair<uint,uint> >V[50005];
        for(uint i=0;i<n*k;i++){
            Gone[i]=false;uint&l=L[i]=0,r=i;
            while(l<r){uint mid=(l+r)>>1;if(T[i]-T[mid]<=v)r=mid;else l=mid+1;}
        }
        for(uint i=0;i<n;i++)V[i].clear();
        for(uint i=0;i<n;i++){
            for(uint j=0;j<k;j++)if(T[A[i][j]]-T[0]<=v&&T[n*k-1]-T[A[i][(u+j)%k]]<=v){
                std::vector<uint>B;
                for(uint t=1;t<k;t++)if(t!=u)B.push_back(A[i][(t+j)%k]);
                V[i].push_back({B[0],B[1]});
            }
            if(V[i].empty())return false;
            for(auto s:V[i])Gone[s.first]=true;
            std::sort(V[i].begin(),V[i].end(),[&](std::pair<uint,uint>a,
                        std::pair<uint,uint>b){return a.second<b.second;});
        }
        for(uint i=0,j=0;i<n*k;i++)if(Gone[i]){
            auto insert=[&](uint id,uint l,uint r)
            {
                std::vector<std::pair<uint,uint> >W;
                for(auto p:V[id])if(p.first>=l&&p.first<r){
                    if(W.empty()||W.back().second<L[p.second])
                        W.push_back({L[p.second],p.second+1});
                    else W.back().second=p.second+1;
                }
                for(auto s:W)S.add(s.first,s.second,1);
            };
            auto kill=[&](uint id,uint l,uint r)
            {
                std::vector<std::pair<uint,uint> >W;
                for(auto p:V[id])if(p.first>=l&&p.first<r){
                    if(W.empty()||W.back().second<L[p.second])
                        W.push_back({L[p.second],p.second+1});
                    else W.back().second=p.second+1;
                }
                for(auto s:W)S.add(s.first,s.second,-1);
            };
            while(T[i]-T[j]>v){
                if(Gone[j])kill(Back[j],j,i),insert(Back[j],j+1,i);
                j++;
            }
            kill(Back[i],j,i),insert(Back[i],j,i+1);
            if(S.v==n)return true;
        }
        return false;
    };
    uint l=0,r=T[n*k-1]-T[0];
    while(l<r){uint mid=(l+r)>>1;if(check(mid))r=mid;else l=mid+1;}
    return l;
}
voi solve(){
    scanf("%u",&n);
    for(uint i=0;i<k;i++)for(uint j=0;j<n;j++)scanf("%u",A[j]+i),T[i*n+j]=i*n+j;
    std::sort(T,T+n*k,[&](uint u,uint v){return A[u%n][u/n]<A[v%n][v/n];});
    for(uint i=0,p;i<n*k;i++)p=T[i],std::swap(A[p%n][p/n],T[i]=i);
    if(k==1){
        printf("%u\n",T[n*k-1]-T[0]);
        return;
    }
    if(k==2){
        for(uint i=0;i<n;i++)if(A[i][0]>A[i][1])std::swap(A[i][0],A[i][1]);
        uint Max=0,Min=-1;
        for(uint i=0;i<n;i++)_max(Max,A[i][0]),_min(Min,A[i][1]);
        printf("%u\n",std::max(T[Max]-T[0],T[n*k-1]-T[Min]));
        return;
    }
    for(uint i=0;i<n;i++)for(uint j=1;j<k;j++)if(!A[i][j]){
        std::vector<uint>B(k);
        for(uint t=0;t<k;t++)B[t]=A[i][(t+j)%k];
        for(uint t=0;t<k;t++)A[i][t]=A[0][t],A[0][t]=B[t];
        break;
    }
    for(uint i=0;i<n;i++)for(uint j=0;j<k;j++)Back[A[i][j]]=i;
    if(k==3){
        uint ans=-1;
        for(uint u=1;u<k;u++)_min(ans,solve3(u));
        printf("%u\n",ans);
        return;
    }
    if(k==4){
        uint ans=-1;
        for(uint u=1;u<k;u++)_min(ans,solve4(u));
        printf("%u\n",ans);
        return;
    }
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#else
#endif
    uint t;scanf("%u%u",&t,&k);
    while(t--)solve();
    return 0;
}

// 那就是希望。
// 即便需要取模，也是光明。