#include <cstdio>
#include <cstring>
using namespace std;
 
#define Nmax 13
#define min(a,b) ((a) < (b) ? (a) : (b))
#define max(a,b) ((a) > (b) ? (a) : (b))
 
int n, t;
int mat[Nmax][Nmax], sir[Nmax];
int d[Nmax][1 << Nmax];
 
void solve()
{
    int i, j, mask, mask1, mask2, mask3, ct, nod, lim;
     
    memset(d, 0x3f, sizeof(d));
    for (i = 1; i <= n; ++i)
        d[i][0] = 0;
    for (mask = 1; mask < 1 << n; ++mask)
        for (nod = 1; nod <= n; ++nod)
            if ((mask >> (nod - 1)) & 1)
            {
                if ((mask ^ (1 << (nod - 1))) == 0)
                {
                    d[nod][mask] = 0;
                    continue;
                }
                ct = 0;
                for (i = 0; i < n; ++i)
                    if (nod != i + 1 && ((mask >> i) & 1))
                        sir[++ct] = i + 1;
                for (mask1 = 1; mask1 < 1 << ct; ++mask1)
                {
                    mask2 = 0;
                    for (i = 1; i <= ct; ++i)
                        if ((mask1 >> (i - 1)) & 1)
                            mask2 += 1 << (sir[i] - 1);
                     
                   
                    mask3 = mask ^ mask2;
                    for (i = 1; i <= ct; ++i)
                        d[nod][mask] = min(d[nod][mask], mat[nod][sir[i]] + max(d[sir[i]][mask2], d[nod][mask3]));
                }
                
            }
             
    printf("%d\n", d[1][(1 << n) - 1]);
}
 
void citire()
 
{
    int i, j;
    scanf("%d\n", &t);
    while (t)
    {
        scanf("%d\n", &n);
        for (i = 1; i <= n; ++i)
            for (j = 1; j <= n; ++j)
                scanf("%d", &mat[i][j]);
        solve();
        --t;
    }
}
 
int main()
{
    freopen("cast.in", "r", stdin);
    freopen("cast.out", "w", stdout);
    citire();
    return 0;
}