#include <bits/stdc++.h>

using namespace std;

#define ST_DIO 0
#if ST_DIO
    #define fin cin
    #define fout cout
#else
    ifstream fin("cast.in");
    ofstream fout("cast.out");
#endif  // ST_DIO

int n, i, j, ii, jj, v[13][13];
int d[(1 << 13) + 2][13];

int main() {
    if(ST_DIO) ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    int t;
    fin >> t;
    while(t--) {
        fin >> n;
        for(i = 1; i <= n; i++) {
            for(j = 1; j <= n; j++) fin >> v[i][j];
        }

        for(i = 0; i < (1 << n); i++) {
            for(j = 1; j <= n; j++) d[i][j] = 1e9 + 7;
        }

        for(i = 1; i <= n; i++) d[1 << (i - 1)][i] = 0;

        for(i = 0; i < (1 << n); i++) {
            for(j = 1; j <= n; j++) {
                if(!(i >> (j - 1) & 1)) continue;

                for(int ii = (i & (i - 1)); ii > 0; ii = ((ii - 1) & i)) {
                    if(ii >> (j - 1) & 1) continue;

                    int rest = (i ^ ii);
                    for(jj = 1; jj <= n; jj++) {
                        if(!(ii >> (jj - 1) & 1)) continue;
                        d[i][j] = min(d[i][j], v[j][jj] + max(d[rest][j], d[ii][jj]));
                    }
                }
            }
        }
        fout << d[(1 << n) - 1][1] << "\n";
    }

    return 0;
}