#include <cstdio>
#include <cstring>

#define inf 1000000000 //un miliard
#define Nmax 16

int n;
int a[Nmax][Nmax];

char viz[Nmax][1 << Nmax];
int c[Nmax][1 << Nmax];

inline int min(int a, int b)
{ return (a < b ? a : b); }

inline int max(int a, int b)
{ return (a > b ? a : b); }

int solve(int k, int conf)
{
    if (viz[k][conf]) return c[k][conf];
    viz[k][conf] = 1;

    int u[Nmax];
    int i, j, nr = 0, cur, val, contra;
    int v1, v2;
    int best = inf;

    for (i = 1; i <= n; ++i) if (i != k)
        if ((conf >> (i-1)) & 1) u[++nr] = i;
    if (nr == 0) return 0;

    for (i = 1; i <= ((1 << nr) -1); ++i)
    {
        cur = 0;
        for (j = 1; j <= nr; ++j)
            if ((i >> (j-1)) & 1)
                cur += 1 << (u[j]-1);
        contra = conf & (~cur);
        
        v2 = solve(k, contra);

        for (j = 1; j <= nr; ++j)
            if ((i >> (j-1)) & 1)
            {
                val = u[j];

                v1 = solve(val, cur);
                best = min(best, a[k][val] + max(v1, v2));
            }
    }
    
    c[k][conf] = best;
    return c[k][conf];
}

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

    int t, i, j;

    for (scanf("%d", &t); t; --t)
    {
        scanf("%d", &n);
        for (i = 1; i <= n; ++i)
        for (j = 1; j <= n; ++j)
            scanf("%d", &a[i][j]);

        memset(viz, 0, sizeof(viz));

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