#include <bits/stdc++.h>

using namespace std;

ifstream in("cast.in");
ofstream out("cast.out");

const int N = 12;
const int INF = 1e7;

int n, t;
int a[N][N];
int dp[1 << N][N]; /*/ dp[mask][root]=costul minim daca am radacina in root, masca mask /*/

void ReadTest() {
  in >> n;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      in >> a[i][j];
  for (int i = 0; i < 1 << n; ++i)
    for (int j = 0; j < n; ++j)
      dp[i][j] = INF;
}

int calc(int mask, int root) {
  if (__builtin_popcount(mask) <= 1)
    return dp[mask][root] = 0;
  if (dp[mask][root] != INF)
    return dp[mask][root];
  for (int fiu = 0; fiu < n; ++fiu) {
    if ((1 << fiu)&mask) {
      if (fiu != root) {
        int ramase = mask ^ (1 << fiu);
        for (int submask = ramase; submask >= 0; submask = (submask - 1)&ramase) {
          int complementara = ramase ^ submask;
          if(complementara & (1<<fiu))
            continue;
          if(!(complementara & (1 << root)))
            continue;
          assert(complementara&(1<<root));
          dp[mask][root] = min(dp[mask][root], a[root][fiu]+max(calc(complementara,root),calc(submask|(1<<fiu),fiu)));
          if (submask == 0)
            break;
        }
      }
    }
  }

  return dp[mask][root];
}

void Solve() {
  out << calc((1 << n) - 1, 0) << '\n';
}
int main() {
  in >> t;
  while (t--) {
    ReadTest();
    Solve();
  }
  return 0;
}