#include <bits/stdc++.h>

using namespace std;

const int nmax = 12;
int mat[nmax][nmax], dp[nmax][1 << nmax], bit[1 << nmax];
// dp[i][mask] = vreau sa transmit din i informatia tuturor calculatoarelor din mask
// bit[mask] = log2(mask) pt mask putere de 2

int main() {
  ifstream fin("cast.in");
  ofstream fout("cast.out");
  for (int i = 0; i < nmax; i++)
    bit[1 << i] = i;
  int t;
  fin >> t;
  while (t--) {
    int n;
    fin >> n;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        fin >> mat[i][j];
    for (int i = 0; i < n; i++)
      for (int mask = 1; mask < (1 << n); mask++)
        dp[i][mask] = 1e9;
    for (int mask = 1; mask < (1 << n); mask++)
      if ((mask & (mask - 1)) == 0)
        dp[bit[mask]][mask] = 0;
      else
        for (int submask = mask; submask > 0; submask = (submask - 1) & mask)
          for (int i = 0; i < n; i++)
            if ((mask & (1 << i)) && !(submask & (1 << i)))
              for (int j = 0; j < n; j++)
                if (submask & (1 << j))
                  dp[i][mask] = min(dp[i][mask], max(dp[i][mask ^ submask], dp[j][submask]) + mat[i][j]);
    fout << dp[0][(1 << n) - 1] << '\n';
  }
  return 0;
}