#include<stdio.h>
#include<algorithm>
const int N=14;
using namespace std;
FILE *f,*g;

int s , s1 , s2;

int sol[N][4100]; int minim;

bool inset[N], insubset[N]; 

int dist[N][N]; int n,t; int aux;

void solve(int j, int i){

    if (i == j || !inset[i]){
        insubset[i]=0;
        solve(j,i+1);
    }
    else{
        
        if (i != n+1 ){
            insubset[i]=0;
            s1+=1<<i;
            solve(j,i+1);
            
            insubset[i]=1;
            s1-=1<<i; s2+=1<<i;
            solve(j,i+1);
            s2-=1<<i;
        }
        else{
            
            int k;
            for(k=1;k<=n;k++)
                if (insubset[k])
                    if (minim > max(sol[j][s1] ,sol[k][s2]) + dist[j][k]) minim= max (sol[j][s1], sol[k][s2]) +dist[j][k];
            
        }
    }
}

int gulu;

void backtracking(int i){
    
    
    if (i != n+1){
        inset[i]=0;
        backtracking(i+1);
        
        inset[i]=1;
        s+=1<<i;
        backtracking(i+1);
        s-=1<<i;
    }

    else
        for(aux=1;aux<=n;aux++)
            if (inset[aux]){
                s1=1<<aux;s2=0;
                minim=1000000000; insubset[aux]=0;
                solve(aux,1);
                sol[aux][s]= minim == 1000000000 ? 0 : minim;
            }
    
}

int main(void){

    f=fopen("cast.in","r");
    g=fopen("cast.out","w");

    int j, k;
    fscanf(f,"%d",&t);
    for(gulu=1;gulu<=t;gulu++){
        
        fscanf(f,"%d",&n); inset[n+1]=1;
        for(j=1;j<=n;j++)
            for(k=1;k<=n;k++)
                fscanf(f,"%lld",&dist[j][k]);
        for(j=1;j<=n;j++)
            for (k=1; k<=(1<<(n+1)); k++) sol[j][k]=0;
        backtracking(1);
        fprintf(g,"%lld\n",sol[1][(1<<(n+1))-2]);
    }

}