#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <vector>

using namespace std; 
#define pb push_back
#define sz(x) (int)(x.size())
#define rall(x) (x).rbegin(), (x).rend()
const int N = 25, MSK = (1 << 25), inf = 1e9;

int n, a[N][N], dp[MSK][N];

void run_case(int test_case) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    dp[0][0] = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int i = 1; i <= n; i++) {
            if (mask & (1 << (i - 1))) {
                if (__builtin_popcount(mask) == 1) {
                    dp[mask][i] = 0;
                } else {
                    dp[mask][i] = inf;
                    for (int s = mask; s; s = (s - 1) & mask) {
                        if (!(s & (1 << (i - 1)))) {
                            for (int j = 1; j <= n; j++) {
                                if (s & (1 << (j - 1))) {
                                    dp[mask][i] = min(dp[mask][i], max(dp[mask ^ s][i], dp[s][j]) + a[i][j]);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        run_case(t);
    }
}