/*
tMin[i][j]=costul minim pentru a conecta nodurile de la indicii din desc binara a lui j avand rad in i
*/
#include <stdio.h>
#include <cstring>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define Nmax 13
#define INF (1 << 30)
using namespace std;
int tComp[Nmax][Nmax], tMin[Nmax][(1 << Nmax)], N, T;
char v[Nmax][(1 << Nmax)];
FILE *fin = fopen("cast.in", "rt");
FILE *fout = fopen("cast.out", "wt");
int solve(int k, int conf)
{   if(v[k][conf]) return tMin[k][conf];
    v[k][conf]=1;
    int contra, i, j, u[Nmax], nr = 0, cur, val, best = INF, v1, v2;
    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,tComp[k][val]+MAX(v1,v2)); //MAX(v1,v2)-ne asiguram ca parcurgem amandoi arborii
            }
    }
    tMin[k][conf]=best;
    return tMin[k][conf];
}
int main()
{   int i=0, j = 0;
    fscanf(fin,"%d",&T);
    while(T--)
    {   memset(v, 0, sizeof(v));
        fscanf(fin, "%d", &N);
        for(i=1;i<=N;++i)
            for(j=1;j<=N;++j)
            fscanf(fin, "%d", &tComp[i][j]);
        fprintf(fout, "%d\n", solve(1, (1 << N) - 1));
    }
    fclose(fout);
    return 0;
}