#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int kMaxN = 15;
const int kInf = numeric_limits<int> :: max() / 2;

int N;
vector<int> Log;
vector<vector<int>> timePairwise;

void Preprocess() {
  Log = vector<int>((1 << kMaxN), 0);
  for(int i = 2; i < (1 << kMaxN); i++) Log[i] = Log[i >> 1] + 1;
}

int Solve() {
  vector<vector<int>> dynProg(N, vector<int>((1 << N), kInf));
  for(int Subset = 1; Subset < (1 << N); Subset++) {
    if(Subset & (Subset - 1)) {
      for(int i = Subset; i > 0; i &= (i - 1)) {
        int u = Log[i & -i];
        for(int subSubset = Subset; subSubset > 0; subSubset = Subset & (subSubset - 1)) {
          for(int j = subSubset; j > 0; j &= (j - 1)) {
            int v = Log[j & -j];
            dynProg[u][Subset] = min(dynProg[u][Subset], timePairwise[u][v] + max(dynProg[v][subSubset], dynProg[u][Subset & (Subset ^ subSubset)]));
          }
        }
      }
    } else dynProg[Log[Subset]][Subset] = 0;
  }
  return dynProg[0][(1 << N) - 1];
}

int main() {
  ifstream f("cast.in");
  ofstream g("cast.out");
  
  Preprocess();
  
  int tCases;
  for(f >> tCases; tCases > 0; tCases--) {
    f >> N;
    timePairwise = vector<vector<int>>(N, vector<int>(N, 0));
    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++)
        f >> timePairwise[i][j];
    g << Solve() << "\n";
  }
  
  return 0;
}