#include <bits/stdc++.h>

using namespace std;

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

const int INF = 1e9;

void minSelf(int &x, int y) {
  if (y < x) {
    x = y;
  }
}

void testCase() {
  int n;
  fin >> n;
  vector<vector<int>> cost(n, vector<int>(n));
  for (auto &it : cost) {
    for (int &x : it) {
      fin >> x;
    }
  }
  vector<vector<int>> dp(n, vector<int>(1 << n, INF));
  for (int i = 0; i < n; ++i) {
    dp[i][1 << i] = 0;
  }
  for (int mask = 3; mask < (1 << n); ++mask) {
    if (__builtin_popcount(mask) >= 2) {
      int left = (mask - 1) & mask;
      while (left) {
        int right = mask ^ left;
        for (int i = 0; (1 << i) <= left; ++i) {
          if (left & (1 << i)) {
            for (int j = 0; (1 << j) <= right; ++j) {
              if (right & (1 << j)) {
                minSelf(dp[i][mask], max(dp[i][left], dp[j][right]) + cost[i][j]);
              }
            }
          }
        }
        left = (left - 1) & mask;
      }
    }
  }
  fout << dp[0][(1 << n) - 1] << '\n';
}

int main() {
  int tests;
  fin >> tests;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  fin.close();
  fout.close();
  return 0;
}