#include <cstdio>
#include <algorithm>

using namespace std;

#define maxn 13
#define inf 1000000000

int t, n, i, j, k, nb;
int conf[maxn], v[maxn][maxn], d[1<<maxn][maxn];

void solve(int conf, int nc, int poz, int c1, int c2)
{
    if(poz==n)
    {
        for(int j=0; j<n; ++j)
            if((c1>>j)&1)
                d[conf][nc]=min(d[conf][nc], v[nc][j]+max(d[c1][j], d[c2][nc]));
        return;
    }

    if((conf>>poz)&1)
    {
        if(poz!=nc)
            solve(conf, nc, poz+1, c1+(1<<poz), c2);
        solve(conf, nc, poz+1, c1, c2+(1<<poz));
    }
    else
        solve(conf, nc, poz+1, c1, c2);
}


int main()
{
    freopen("cast.in", "r", stdin);
    freopen("cast.out", "w", stdout);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j)
                scanf("%d", &v[i][j]);

        for(int i=1; i<(1<<n); ++i)
        {
            nb=0;
            for(int j=0; j<n; ++j)
            {
                conf[j]=(i>>j)&1;
                nb+=conf[j];
                d[i][j]=inf;
            }

            for(int j=0; j<n; ++j)
            {
                if(conf[j]==0)
                    continue;
                if(nb==1)
                    d[i][j]=0;
                else
                    solve(i, j, 0, 0, 0);
            }
        }

        printf("%d\n", d[(1<<n)-1][0]);
    }

    return 0;
}