#include <algorithm>
#include <fstream>
#include <queue>

using namespace std;

const int MOD = 100003;
const int INF = 1e9;

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

int d[1<<12][12];
int c[13][13];

int n, t;
int i, j, b, k;

int main()
{
  in >> t;

  for(int test = 1; test <= t;test++) {
    in >> n;

    for(i = 0; i < n; i++)
      for(j = 0; j < n; j++)
        in >> c[i][j];

    for(k = 1; k < (1 << n); k++)
      for(i = 0; i < n; i++)
        if(k & (1 << i)) {
          if(k == (1 << i)) {
            d[k][i] = 0;
            continue;
          }

          d[k][i] = INF;

          for(b = k - (1 << i); b; b = (b - 1) & (k - (1 << i)))
            for(j = 0; j <= n; j++)
              if(b & (1 << j))
                d[k][i] = min(d[k][i], c[i][j] + max(d[b][j], d[k ^ b][i]));
        }

    out << d[(1 << n) - 1][0] << '\n';
  }

  in.close();
  out.close();

  return 0;
}