#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;

#if 0
#define int ll
#define uint ull
#endif

/**
 * Problem: Cast
 * URL: https://infoarena.ro/problema/cast
 * TL: 2000 ms
 * ML: 20 MB
 *
 * Good Luck!
*/

void preinit() {
}

struct state {
    vector<int> t, c;
};

void tc() {
    int n;
    cin >> n;
    vector<vector<int>> mat(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> mat[i][j];
        }
    }

    vector<vector<int>> dp((1 << (n + 1)), vector<int>(n + 1, 1e6));
    for (int i = 1; i <= n; i++) {
        dp[(1 << i)][i] = 0;
    }
    for (int m1 = 0; m1 < (1 << (n + 1)); m1++) {
        for (int i = 1; i <= n; i++) {
            if ((1 << i) & (m1)) {
                for (int m2 = 0; m2 < m1; m2++) {
                    if (m1 & m2) continue;

                    for (int j = 1; j <= n; j++) {
                        if ((1 << j) & (m2)) {
                            dp[m1 | m2][i] =
                                min(dp[m1 | m2][i],
                                    max(dp[m1][i], dp[m2][j]) + mat[i][j]);
                            dp[m1 | m2][j] =
                                min(dp[m1 | m2][j],
                                    max(dp[m1][i], dp[m2][j]) + mat[j][i]);
                        }
                    }
                }
            }
        }
    }

    cout << dp[(1 << (n + 1)) - 2][1] << '\n';
}

#define MTC 1
#define FIO 1
#define FN "cast"

signed main() {
#if FIO == 1 && !defined(LOCAL)
    (void)freopen(FN ".in", "r", stdin);
    (void)freopen(FN ".out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    preinit();
#if MTC == 1
    signed tt;
    cin >> tt;
    while (tt--) tc();
#else
    tc();
#endif
    return 0;
}