/*
    Tmin[i][j] - costul minim pentru a conecta nodurile de la indicii din desc binara a lui j avand rad in i
    MaxN = nr maxim de calculatoare
    MaxT = nr maxim de teste
    
    -exista un drum intre oricare doua noduri
    -tMin[i][j] = 
*/

#include <stdio.h>
#include <cstring>
#include <vector>
#define REP(i, n) for (i = 0; i < n; i++)
#define REPV(i, a, b) for (i = (a); i <= (b); i++)
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define MaxN 13
#define INF (1 << 30)

using namespace std;


int tComp[MaxN][MaxN], tMin[MaxN][(1 << MaxN)], N, T;
char v[MaxN][(1 << MaxN)];
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;
    
    //fprintf(fout, "%d %d\n", k, conf);
        
    int contra, i, j, u[MaxN], nr = 0, cur, val, best = INF, v1, v2;
    
    REPV(i, 1, N)
        if (i != k) 
            if ((conf >> (i - 1)) & 1)
                u[++nr] = i;
    if (nr == 0) return 0;
    
    /*REPV(i, 1, nr)
        fprintf(fout, "%d ", u[i]);
    fprintf(fout, "\n");*/
        
    REPV(i, 1, (1 << nr) - 1)
    {
        cur = 0;
        REPV(j, 1, nr)
            if ((i >> (j - 1)) & 1)
                cur += (1 << (u[j] - 1));
        
        contra = conf & (~cur);
        v2 = solve(k, contra);
        
        REPV(j, 1, nr)
            if ((i >> (j - 1)) & 1)
            {
                val = u[j];
                v1 = solve(val, cur); // 
                //fprintf(fout, "%d %d %d\n", conf, cur, contra);
                //fprintf(fout, "v1, v2, k, val, tComp, best: %d %d %d %d %d %d\n", v1, v2, k, val, tComp[k][val], best);
                best = MIN(best, tComp[k][val] + MAX(v1, v2)); // MAX(v1, v2) - ne asiguram ca parcurgem amandoi arborii
            } 
    }
    tMin[k][conf] = best;
    //fprintf(fout, "best updated: %d\n", best);
    //fprintf(fout, "tMin: %d %d %d\n", k, conf, tMin[k][conf]);
    return tMin[k][conf];
}
    
int main()
{
    int i = 0, j = 0;
    
    fscanf(fin, "%d", &T);
    for (; T; T--)
    {
        memset(v, 0, sizeof(v));
        fscanf(fin, "%d", &N);
        REPV(i, 1, N) REPV(j, 1, N) fscanf(fin, "%d", &tComp[i][j]);
        /*REPV(i, 1, N) 
        {
            REPV(j, 1, N) fprintf(fout, "%d ", tComp[i][j]);
            fprintf(fout, "\n");
        }*/
        fprintf(fout, "%d\n", solve(1, (1 << N) - 1));
    }
    
    fclose(fin);
    fclose(fout);
    
    return 0;
}