#include<cstdio>
#include<vector>
#include<utility>
#define N 12
#define MULT 1000000000
using namespace std;

int dp[(1<<N)][N];
int mat[N][N];

vector<int> part;
int stare;

void fpart(int i,int mask=0){
    if (i==-1){
        if (mask!=0) part.push_back(mask);
        return ;
    }

    fpart(i-1,mask);
    if ((1<<i)&stare) fpart(i-1,mask^(1<<i));
}

int solve(int n){
    int i,j;

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            scanf ("%d",&mat[i][j]);

    for(i=1;i<(1<<n);i++)
        for(j=0;j<n;j++)
            if ((1<<j)&i){
                dp[i][j]=MULT;

                part.clear();
                stare=(i^(1<<j));
                fpart(n-1);

                for(int ii=0;ii<part.size();ii++){
                    int mask=part[ii];

                    for(int jj=0;jj<n;jj++)
                        if (mask&(1<<jj)) dp[i][j]=min(dp[i][j],mat[j][jj]+max(dp[mask][jj],dp[i^mask][j]));
                }

                if (dp[i][j]==MULT) dp[i][j]=0;
            }

    return dp[(1<<n)-1][0];
}

int main(){
    freopen ("cast.in","r",stdin);
    freopen ("cast.out","w",stdout);
    int n,t;

    scanf ("%d",&t);
    for(;t>0;t--){
        scanf ("%d",&n);
        printf ("%d\n",solve(n));
    }

    return 0;
}