#include<cstdio>
#include<cstring>
#include<vector>
#define infile "cast.in"
#define outfile "cast.out"
#define nMax 12
#define cMax 10013
#define inf 1<<30

using namespace std;

int dp[1<<nMax];
int ad[nMax][nMax];
int n;

vector <int> v[nMax];
bool vz[nMax];
int le[nMax];
int ri[nMax];

void read() {
  scanf("%d\n", &n);
  for(int i = 0; i < n; ++i)
    for(int j = 0; j < n; ++j)
      scanf("%d", &ad[i][j]);
}

bool pairUp(int x) {
  if(vz[x]) return false;
  vz[x] = true;
  for(unsigned i = 0; i < v[x].size(); ++i)
    if(!ri[v[x][i]] || pairUp(ri[v[x][i]] - 1)) {
      ri[v[x][i]] = x + 1;
      le[x] = v[x][i] + 1;
      return true;
    }
  return false;
}

bool verif(int a, int b, int co) {

  for(int i = 0; i < n; ++i) {
    v[i].clear();
    le[i] = ri[i] = 0;
  }

  // init graph
  for(int i = 0; i < n; ++i)
    if((a>>i) & 1)
      for(int j = 0; j < n; ++j)
        if((b>>j) & 1 && ad[i][j] <= co)
          v[i].push_back(j);

  int count = 0;
  bool ok = true;

  while(ok) {
    ok = false;
    memset(vz, 0, sizeof(vz));
    for(int i = 0; i < n; ++i)
      if(!le[i] && pairUp(i))
        count++, ok = true;
  }

  for(int i = 0; i < n; ++i)
    if((b>>i) & 1)
      count--;

  return count == 0;
}

void solve() {

  memset(dp, 0, sizeof(dp));
  dp[1] = 0;

  for(int i = 2; i < (1<<n); ++i) {
    dp[i] = inf;
    for(int j = (i - 1) & i; j; j = (j-1)&i) {
      int le = 0, ri = cMax;
      while(le <= ri) {
        int mi = (le+ri) / 2;
        if(verif(i-j, j, mi)) ri = mi-1, dp[i] = min(dp[i], dp[i-j] + mi);
        else le = mi+1;
      }
    }
  }
}

void write() {
  printf("%d\n", dp[(1<<n)-1]);
}

int main() {
  freopen(infile, "r", stdin);
  freopen(outfile, "w", stdout);

  int t;
  scanf("%d\n", &t);
  while(t--) {
    read();
    solve();
    write();
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}