#include<stdio.h>
#include<algorithm>
using namespace std;
 
#define NMAX 13
#define INF 1000000005
 
int n,cost[NMAX][NMAX],biti[NMAX],solutie;
int t,dinamica[1<<13][NMAX],nr_biti;
 
int main ()
{
    int i,j,bit,indice_vecin,vecin,indice_tata,tata,conf;
     
    freopen("cast.in","r",stdin);
    freopen("cast.out","w",stdout);
     
    scanf("%d",&t);
     
    for(; t; t--)
    {
        scanf("%d",&n);
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                scanf("%d", &cost[i][j]);
        for(i = 1; i < (1<<n); i++)        
        {
            nr_biti = 0;
            for(bit = 1; bit <= n; bit++)
                if(i & (1 << (bit - 1)))
                    biti[++nr_biti] = bit;
            if(nr_biti == 1)    
            {
                dinamica[i][biti[1]] = 0;
                continue;
            }   
                     
            for(indice_tata = 1; indice_tata <= nr_biti; indice_tata++)
            {
                tata = biti[indice_tata];
                if((i&1) && tata != 1)
                    continue;
                     
                dinamica[i][tata] = INF;
                for(j = 1; j < (1 << nr_biti); j++)
                {
                    if(j & (1 << (indice_tata - 1)))
                        continue;
                         
                    conf = 0;
                    for(bit = 1; bit <= nr_biti; bit++)
                        if(j & (1 << (bit - 1)))
                            conf += (1 << (biti[bit] - 1));
                             
                    for(indice_vecin = 1; indice_vecin <= nr_biti; indice_vecin++)   
                    {
                        vecin = biti[indice_vecin];             
                        if(!(conf & (1 << (vecin - 1))))
                            continue;
                        dinamica[i][tata] = min(dinamica[i][tata], cost[tata][vecin] + max(dinamica[i - conf][tata], dinamica[conf][vecin]));   
                    }
                }
            }   
        }   
        printf("%d\n",dinamica[(1 << n) - 1][1]);
    }
     
    return 0;
}