#include<bits/stdc++.h> using namespace std; #define int long long const int INF=1e18; int n,K,T,fac[5]={1,1,2,6,24}; struct perm{int p[5];}P[25],cp[55]; perm operator +(perm A,perm B){perm C;for(int i=1;i<=K;i++)C.p[i]=A.p[B.p[i]];return C;} int Rank(perm A){int res=1;for(int i=1;i<=K;i++){for(int j=i+1;j<=K;j++)if(A.p[i]>A.p[j])res+=fac[K-i];}return res;} #define VI vector<int> #define VVI vector<VI> struct state{VVI A;int d,dx;state(){A.resize(3);d=dx=0;}state(VVI B,int D,int DX){A=B,d=D,dx=DX;}}; bool operator <(state A,state B){return A.d>B.d;} map<VVI,int> dis[26]; priority_queue<state> Q; int f[25][25],g[25][25][25],h[55][25],d[25][25]; bool check(VVI B,int d,int dx){ for(int i=0;i<=dx;i++)if(dis[i].count(B)&&dis[i][B]<=d)return 0; return dis[dx][B]=d,1; } signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>T>>n>>K;int fK=fac[K],F=24; for(int i=1;i<=K;i++)P[1].p[i]=i; for(int i=2;i<=fac[K];i++){ for(int j=1;j<=K;j++)P[i].p[j]=P[i-1].p[j]; next_permutation(P[i].p+1,P[i].p+K+1); } state S;for(int i=1;i<=K+1;i++)S.A[0].push_back(i); Q.push(S);dis[0][S.A]=0; while(Q.size()){ auto [A,d,dx]=Q.top();Q.pop(); if(d!=dis[dx][A])continue; for(int i=0;i<3;i++){ if(A[i].empty())continue; for(int j=0;j<3;j++){ if(i==j)continue; if(A[j].empty()||(A[j].back()!=K+1||A[i].back()==K+1)){ int dt=(A[i].back()<K+1),dtx=1-dt; VVI B=A;B[j].push_back(B[i].back());B[i].pop_back(); if(check(B,d+dt,dx+dtx))Q.push({B,d+dt,dx+dtx}); } } } } for(int i=0;i<25;i++)for(int j=0;j<25;j++)for(int k=0;k<25;k++)f[j][k]=g[i][j][k]=INF; for(int i=0;i<=F;i++){ for(int j=1;j<=fK;j++){ VVI A(3);for(int k=1;k<=K;k++)A[2].push_back(P[j].p[k]); A[2].push_back(K+1); if(!dis[i].count(A))f[i][j]=INF; else f[i][j]=dis[i][A]; g[1][i][j]=f[i][j]; } } for(int i=1;i<=fK;i++)for(int j=1;j<=fK;j++)d[i][j]=Rank(P[i]+P[j]); for(int i=2;i<=F;i++)for(int j=1;j<=F;j++)for(int k=1;k<=fK;k++)for(int l=0;l<=j;l++)for(int m=1;m<=fK;m++)g[i][j][d[k][m]]=min(g[i][j][d[k][m]],g[i-1][j-l][k]+f[l][m]); for(int t=1;t<=T;t++){int res=INF; for(int j=1;j<=n;j++)for(int k=1;k<=K;k++)cin>>cp[j].p[k]; for(int i=0;i<=n;i++)for(int j=0;j<25;j++)h[i][j]=INF; for(int j=0;j<25;j++)h[n+1][j]=0; for(int i=n;i>=1;i--){int ri=Rank(cp[i]); for(int j=1;j<=F;j++)for(int p=0;p<=F;p++)for(int l=0;l<=F-p;l+=2)h[i][j]=min(h[i][j],h[i+1][p]+((1ll<<n-i)-1)*K*l+g[j][p+l][ri]); } for(int i=1;i<=fK;i++)res=min(res,h[1][i]);cout<<res<<endl; if(t<T)cin>>n>>K; } return 0; }