#include <bits/stdc++.h>
#define cin fin
#define cout fout

using namespace std;

ifstream fin("cast.in");
ofstream fout("cast.out");

const int NMAX = 12;
const int INF = 1e9;

int n;
int a[NMAX + 1][NMAX + 1];
int dp[1 << NMAX][NMAX + 1];

void test_case() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    for(int mask = 0; mask < (1 << n); mask++) {
        for(int i = 0; i < n; i++) {
            dp[mask][i] = INF;
        }
    }
    for(int i = 0; i < n; i++) {
        dp[1 << i][i] = 0;
    }
    for(int mask = 1; mask < (1 << n); mask++) {
        if(__builtin_popcount(mask) == 1) {
            continue;
        }
        for(int i = 0; i < n; i++) {
            if(!(mask >> i & 1)) {
                continue;
            }
            int other_mask = mask ^ (1 << i);
            for(int submask = other_mask; submask; submask = (submask - 1) & other_mask) {
                for(int j = 0; j < n; j++) {
                    if(!(submask >> j & 1)) {
                        continue;
                    }
                    dp[mask][i] = min(dp[mask][i], max(dp[submask][j], dp[mask ^ submask][i]) + a[i][j]);
                }
            }
        }
    }
    cout << dp[(1 << n) - 1][0] << '\n';
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        test_case();
    }
    return 0;
}