#include <iostream>
#include <fstream>
#include <fstream>
#include <vector>
#include <cassert>

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

using ll = long long;

#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 12;
int const inf = 10000;

int f[1 + nmax][1 + nmax];
int dp[1 + nmax][1 << nmax];

int lg(int number) {
  return __builtin_ctz(number);
}

void solve() {
  int n;
  in >> n;
  for(int i = 0;i < n; i++)
    for(int j = 0;j < n; j++)
      in >> f[i][j];
  for(int i = 0; i < n; i++)
    for(int j = 0; j < (1 << n); j++)
      dp[i][j] = nmax * inf;
  for(int i = 0; i < n; i++)
    dp[i][0] = 0;
  int full = (1 << n) - 1;
  
  for(int mask = 2; mask < (1 << n); mask += 2) {
    for(int mask2 = (mask ^ full); 0 < mask2; mask2 &= (mask2 - 1)) {
      int pos = lg(mask2);
      for(int mask3 = mask; 0 < mask3; mask3 &= (mask3 - 1)) {
        int sec = lg(mask3);
        int bigmask = (mask ^ (1 << sec));
        for(int submask = bigmask; 0 <= submask; submask = ((submask - 1) & bigmask)) {
          dp[pos][mask] = std::min(dp[pos][mask], f[pos][sec] + std::max(dp[sec][submask], dp[pos][bigmask ^ submask]));
          if(0 == submask)
            break;
        }
      }
    }
  }

  out << dp[0][full - 1] << '\n';
}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int t;
  in >> t;
  for(int testcase = 1; testcase <= t; testcase++)
    solve();
}