#include <bits/stdc++.h>

using namespace std;

const int MAXN = 12;
const int INF = 0x3f3f3f3f;

int dp[MAXN][1 << MAXN], mat[MAXN][MAXN];

int main()
{
    int t;
    ifstream fin("cast.in");
    fin >> t;
    ofstream fout("cast.out");
    for (t = t; t > 0; --t) {
      int n;
      fin >> n;
      for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
          fin >> mat[i][j];
      memset(dp, INF, sizeof dp);
      for (int i = 0; i < n; ++i)
        dp[i][1 << i] = 0;
      for (int conf = 2; conf < (1 << n); ++conf)
        if (conf & (conf - 1))
          for (int root = 0; root < n; ++root)
            if (conf & (1 << root)) {
              for (int node = 0; node < n; ++node)
                if ((node ^ root) && (conf & (1 << node)))
                  dp[root][conf] = min(dp[root][conf], dp[node][conf ^ (1 << root)] + mat[root][node]);
              for (int aux = conf; aux > 0; aux = (conf & (aux - 1)))
                for (int node = 0; node < n; ++node)
                  if ((aux & (1 << root)) == 0 && (node ^ root) && (aux & (1 << node)))
                    dp[root][conf] = min(dp[root][conf], mat[root][node] + max(dp[node][aux], dp[root][conf ^ aux]));
            }
      fout << dp[0][(1 << n) - 1] << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}