#include <fstream>
#include <algorithm>
#include <iostream>

using namespace std;

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

int N;
vector<int> Key;
vector<int> fiSet;
vector<int> seSet;
vector<int> timeGroups;
vector<int> dynProg;
vector<int> powersOf3;
vector<int> powersOf2;
vector<vector<int>> timePairwise;

void getTransmissionTime(
 int const backStep, 
 int const stdKey) {
  if(backStep == N) {
    if(seSet.empty()) timeGroups[stdKey] = 0;
    else if(!fiSet.empty()) {
      if(fiSet.size() == 1) {
        timeGroups[stdKey] = 0;
        for(const int &j: seSet)
          timeGroups[stdKey] += timePairwise[fiSet[0]][j];
      } else {
        for(const int &i: fiSet) {
          for(const int &j: seSet) {
            int subsetKey = stdKey - powersOf3[i] - 2 * powersOf3[j];
            timeGroups[stdKey] = min(timeGroups[stdKey], max(timeGroups[subsetKey], timePairwise[i][j]));
          }
        }
      }
    }
  } else {
    Key[backStep] = 0;
    getTransmissionTime(backStep + 1, stdKey);
    Key[backStep] = 1;
    fiSet.push_back(backStep);
    getTransmissionTime(backStep + 1, stdKey + powersOf3[backStep]);
    fiSet.pop_back();
    Key[backStep] = 2;
    seSet.push_back(backStep);
    getTransmissionTime(backStep + 1, stdKey + 2 * powersOf3[backStep]);
    seSet.pop_back();
  }
}

void getDynProg(
 int const backStep,
 int const stdKey,
 int const base2Key,
 int const otherKey) {
  if(backStep == N) {
    if(base2Key != 1)
      dynProg[base2Key] = min(dynProg[base2Key], dynProg[otherKey] + timeGroups[stdKey]);
  } else {
    Key[backStep] = 0;
    getDynProg(backStep + 1, stdKey, base2Key, otherKey);
    Key[backStep] = 1;
    getDynProg(backStep + 1, stdKey + powersOf3[backStep], base2Key + powersOf2[backStep], otherKey + powersOf2[backStep]);
    Key[backStep] = 2;
    getDynProg(backStep + 1, stdKey + 2 * powersOf3[backStep], base2Key + powersOf2[backStep], otherKey);
  }
}

int Solve() {
  timeGroups = vector<int>(powersOf3[N], kInf);
  Key = vector<int>(N, 0);
  getTransmissionTime(0, 0);
  Key = vector<int>(N, 0);
  dynProg = vector<int>(powersOf2[N], kInf);
  dynProg[1] = 0;
  getDynProg(0, 0, 0, 0);
  return dynProg[powersOf2[N] - 1];
}

void Preprocess() {
  powersOf3 = powersOf2 = vector<int>(kMaxN, 1);
  for(int i = 1; i < kMaxN; i++) {
    powersOf3[i] = powersOf3[i - 1] * 3;
    powersOf2[i] = powersOf2[i - 1] * 2;
  }
}

int main() {
  ifstream f("cast.in");
  ofstream g("cast.out");
  
  Preprocess();
  
  int tCase;
  for(f >> tCase; tCase > 0; tCase--) {
    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;
}