#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
  
const int N = 14;
const int inf = 10000000;
  
int n, c[N][N], d[N][1<<N];
  
int din(int nod, int conf) {
    if(d[nod][conf] != inf)
        return d[nod][conf];
      
    vector<int> el;
    int i, j, confn;
      
    for(i = 0; i < n; ++i)
        if((conf & (1<<i)) && nod != i)
            el.push_back(i);
      
    for(i = 0; i < (1<<el.size()); ++i) {
        confn = 0;
          
        for(j = 0; j < el.size(); ++j)
            if(i & (1<<j))
                confn |= (1<<el[j]);
          
        for(j = 0; j < el.size(); ++j)
            if(i & (1<<j))
                d[nod][conf] = min(d[nod][conf],
                                   max(din(nod, conf ^ confn), din(el[j], confn)) + c[nod][el[j]]);
    }
      
    return d[nod][conf];
}
  
void solve() {
    int i, j;
      
    cin >> n;
      
    for(i = 0; i!=n; ++i)
        for(j = 0; j!=n; ++j)
            cin >> c[i][j];
      
    for(i = 0; i!=n; ++i) {
        for(j = 0; j < (1<<n); ++j)
            d[i][j] = inf;
        d[i][1<<i] = 0;
    }
      
    cout << din(0, (1<<n) - 1) << "\n";
}
  
int main() {
    int t;
      
    freopen("cast.in", "r", stdin);
    freopen("cast.out", "w", stdout);
      
    cin >> t;
      
    while(t--)
        solve();
      
    return 0;
}