#include <fstream>
#define DIM (1<<13)
#define DIMN 13
#define INF 2000000000
using namespace std;

ifstream fin ("cast.in");
ofstream fout ("cast.out");
int d[DIM][DIMN],a[DIMN][DIMN],p[DIM];
int t,n,i,j,nr1,nr2,total;
void back (int pas){
    if (pas == n)
        return;
    for (int i=0;i<=2;i++){
        if (i == 1)
            nr1 += (1<<pas);
        else {
            if (i == 2)
                nr2 += (1<<pas);
        }

        total = (nr1 | nr2);
        if (p[total])
            d[total][p[total]-1] = 0;
        else {
            for (int x=0;x<=pas;x++){
                if ( (nr1>>x)&1 )
                    for (int y=0;y<=pas;y++)
                        if ((nr2>>y)&1){
                            d[total][x] = min (d[total][x],max(d[nr1][x],d[nr2][y])+a[x][y]);
                            d[total][y] = min (d[total][y],max(d[nr1][x],d[nr2][y])+a[y][x]);
                        }
            }
        }
        back (pas+1);
        if (i == 1)
            nr1 -= (1<<pas);
        else
            if (i == 2)
                nr2 -= (1<<pas);
    }
}
int main (){

    fin>>t;
    for (;t--;){
        fin>>n;
        for (i=0;i<n;i++)
            for (j=0;j<n;j++)
                fin>>a[i][j];
        for (i=1;i<(1<<n);i++)
            for (j=0;j<n;j++)
                d[i][j] = INF;
        for (i=0;i<=n;i++)
            p[(1<<i)] = i+1;
        nr1 = nr2 = 0;
        back (0);
        fout<<d[(1<<n)-1][0]<<"\n";
    }



    return 0;
}