# include <algorithm>
# include <cstdio>
# include <cstring>
# include <vector>
using namespace std;

const char *FIN = "cast.in", *FOU = "cast.out";
const int MAX = 12;

int N, T, dp[1 << MAX][MAX], time[MAX][MAX];

int solve (int state, int poz) {
    if (dp[state][poz] < 0x3f3f3f3f) return dp[state][poz];

    vector <int> vec;
    for (int i = 0; i < N; ++i)
        if (i != poz && (state & (1 << i)))
            vec.push_back (i);
    for (int bit = 0, size = vec.size (); bit < (1 << size); ++bit) {
        int newstate = 0;
        for (vector <int> :: iterator it = vec.begin (); it != vec.end (); ++it)
            if (bit & (1 << (it - vec.begin ())))
                newstate |= 1 << *it;
        for (vector <int> :: iterator it = vec.begin (); it != vec.end (); ++it)
            if (newstate & (1 << *it))
                dp[state][poz] = min (dp[state][poz], time[poz][*it] + max (solve (state ^ newstate, poz),
                                                                            solve (newstate, *it)));
    }
    return dp[state][poz];
}

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    for (scanf ("%d", &T); T; --T) {
        scanf ("%d", &N), memset (dp, 0x3f, sizeof (dp));
        for (int i = 0; i < N; ++i) {
            dp[1 << i][i] = 0;
            for (int j = 0; j < N; ++j)
                scanf ("%d", time[i] + j);
        }
        printf ("%d\n", solve ((1 << N) - 1, 0));
    }
}