#include<cstdio>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<bitset>
#include<deque>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<unordered_map>

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

const int nmax = 13;
const int lmax = (1 << 12) + 5;
const int inf = 1 << 30;

int t, n, i, j, cost[nmax][nmax], dp[lmax][nmax];

bool is(int x, int mask)
{
    return ((1 << x) & mask);
}

int solve(int mask, int root)
{
    if((1 << root) == mask)
        return 0;

    if(dp[mask][root] != -1)
        return dp[mask][root];

    vector<int> v;

    for(int i = 0; i < n; i++)
        if(i != root && is(i, mask))
            v.pb(i);

    int N = v.size();
    int lim = 1 << N;

    dp[mask][root] = inf;

    for(int i = 1; i < lim; i++)
    {
        int submask = 0;
        for(int j = 0; j < N; j++)
            if(is(j, i))
                submask += (1 << v[j]);

        for(int j = 0; j < n; j++)
            if(is(j, submask))
                dp[mask][root] = min(dp[mask][root], cost[root][j] + max(solve(submask, j), solve(mask - submask, root)));
    }

    return dp[mask][root];
}

int main()
{
    freopen("cast.in", "r", stdin);
    freopen("cast.out", "w", stdout);

    scanf("%d", &t);

    for(; t; t--)
    {
        scanf("%d", &n);

        for(i = 0; i < n; i++)
            for(j = 0; j < n; j++)
                scanf("%d", &cost[i][j]);

        memset(dp, -1, sizeof(dp));
        printf("%d\n", solve((1 << n) - 1, 0));
    }

    return 0;
}