#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int NMAX = 12;
const int INF = 2000000000;

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

int main()
{
    freopen("cast.in", "r", stdin);
    freopen("cast.out", "w", stdout);
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        scanf("%d", &n);
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                scanf("%d", &a[i][j]);
        for(int i=0; i<n; i++)
            for(int j=0; j<(1<<n); j++)
                dp[i][j] = INF;
        for(int i=0; i<n; i++)
            dp[i][1<<i] = 0;
        for(int conf=1; conf<(1<<n); conf++)
            for(int i=0; i<n; i++)
                if(conf & (1<<i))
                {
                    int x = conf ^ (1<<i);
                    for(int subconf=x; subconf>0; subconf = (subconf-1) & x)
                    {
                        for(int j=0; j<n; j++)
                            if(subconf & (1<<j))
                                dp[i][conf] = min(dp[i][conf], a[i][j] + max(dp[j][subconf], dp[i][conf ^ subconf]));
                    }
                }
        printf("%d\n", dp[0][(1<<n)-1]);
    }
    return 0;
}