#include<bits/stdc++.h> using namespace std; #define ll long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) ll rd() { ll x = 0, f = 1; char ch = getchar(); while (ch > '9' || ch < '0') { if (ch == '-') f = -1; ch = getchar(); } do x = x * 10 + ch - 48, ch = getchar(); while (ch >= '0' && ch <= '9'); return x * f; } void wr(ll x) { if (x > 9) wr(x / 10); putchar(x % 10 + 48); } const int K = 7, N = 25, p[6] = {0, 1, 2, 3, 4, 0}; int t, n, k, fac[5] = {0, 1, 2, 6, 24}; map<vector<vector<int>>, int> mp[N]; int tr[N][N], mul[N][N], f[N][N][N]; ll g[55][N]; struct P { int a[K]; void in() { rep(i, 1, k) a[i] = rd(); } int getid() { int res = 0; rep(i, 1, k) { int sum = 0; rep(j, i, k) sum += a[i] > a[j]; res += sum * fac[k - i]; } return res + 1; } bool operator < (const P&x) const { int i = 1; for (; i <= k && a[i] == x.a[i]; i++); return i <= k && a[i] < x.a[i]; } int&operator[](const int&i) { return a[i]; } P operator * (const P&x) { P ans; rep(i, 1, k) ans[i] = a[x.a[i]]; return ans; } } pre[N], a[55]; struct sta { vector<int> a[3]; int x, y; // 最短路 bool work() { per(i, x, 0) { auto it = mp[i].find(vector<vector<int>>(a, a + 3)); if (it != mp[i].end() && it->second <= y) return 0; } mp[x][vector<vector<int>>(a, a + 3)] = y; return 1; } }; queue<sta> q; ll F(int x) { return x < 1 << 24 ? x : 1ll << 60; } void solve() { memset(g[n + 1], 0, sizeof g[n + 1]); per(i, n, 1) { memset(g[i], 50, sizeof g[i]); int id = a[i].getid(); rep(j, 0, N - 1) rep(p, 0, N - 1) for (int l = 0; p + l < N; l += 2) g[i][j] = min(g[i][j], g[i + 1][p] + ((1ll << (n - i)) - 1) * l * k + F(f[j][id][p + l])); } ll ans = 1ll << 60; rep(i, 0, N - 1) ans = min(ans, g[1][i]); wr(ans), putchar('\n'); } signed main() { t = rd(), n = rd(), k = rd(); memcpy(pre[1].a + 1, p + 1, k << 2); rep(i, 2, fac[k]) pre[i] = pre[i - 1], next_permutation(pre[i].a + 1, pre[i].a + k + 1); //末尾的 0 表示更高的若干数 q.push((sta) { vector<int>(pre[1].a + 1, pre[1].a + k + 2), {}, {}, 0, 0 }); q.front().work(); while (q.size()) { sta u = q.front(), v; q.pop(); rep(i, 0, 2) if (!u.a[i].empty()) rep(j, 0, 2) if (i != j && (u.a[i].back() == 0 || (u.a[j].empty() || u.a[j].back() > 0))) { v = u; v.a[j].push_back(v.a[i].back()); (v.a[i].back() ? v.y : v.x)++; v.a[i].pop_back(); if (v.work()) q.push(v); } } int a[6]; memcpy(a, p, sizeof a); memset(tr, 10, sizeof tr); rep(j, 1, fac[k]) rep(i, 0, N - 1) { auto it = mp[i].find({{}, {}, vector<int>(pre[j].a + 1, pre[j].a + k + 2)}); if (it != mp[i].end()) tr[i][j] = it->second; } rep(i, 1, fac[k]) rep(j, 1, fac[k]) mul[i][j] = (pre[i] * pre[j]).getid(); //背包 memset(f, 10, sizeof f); rep(i, 1, fac[k]) rep(j, 0, N - 1) f[1][i][j] = tr[j][i]; rep(i, 1, N - 1) rep(j, 1, fac[k]) rep(l, 1, N - 1) rep(r, 0, N - 1 - l) rep(p, 1, fac[k]) f[i + 1][mul[j][p]][l + r] = min(f[i + 1][mul[j][p]][l + r], f[i][j][l] + tr[r][p]); while (t--) { rep(i, 1, n) ::a[i].in(); solve(); if (t) n = rd(), k = rd(); } return 0; }