#include<bits/stdc++.h>

using namespace std;
const int NMAX=13,buffsize=1<<13,MOD=31607;
typedef long long ll;
ofstream fout("cast.out");
FILE* fin;
char buff[buffsize];
int buffpos=buffsize;
int read(){
    if(buffpos==buffsize) fread(buff,1,buffsize,fin),buffpos=0;
    int n=0;
    while(buff[buffpos]<'0' || buff[buffpos]>'9'){
        ++buffpos;
        if(buffpos==buffsize) fread(buff,1,buffsize,fin),buffpos=0;
    }
    while(buff[buffpos]>='0' && buff[buffpos]<='9'){
        n=(n<<1)+(n<<3)+(buff[buffpos]^48);
        ++buffpos;
        if(buffpos==buffsize) fread(buff,1,buffsize,fin),buffpos=0;
    }
    return n;
}

int dp[1<<NMAX][NMAX],b[NMAX][NMAX];
void tc(){
    int n=read();
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) b[i][j]=read();

    for(int msk=1;msk<(1<<n);msk++) for(int i=0;i<n;i++) dp[msk][i]=1e6;
    for(int i=0;i<n;i++) dp[0][i]=0;

    for(int msk=2;msk<(1<<n);msk+=2){
        for(int root=0;root<n;root++){
            if(msk>>root&1) continue;

            for(int root2=0;root2<n;root2++){
                if(!(msk>>root2&1)) continue;
                int children=msk^(1<<root2);

                for(int submask=children;submask>=0;submask=(submask-1)&children){
                    dp[msk][root]=min(dp[msk][root],max(dp[children^submask][root],dp[submask][root2])+b[root][root2]);
                    if(submask==0) break;
                }
            }
        }
    }
    fout<<dp[(1<<n)-2][0]<<'\n';
}
int main(){
    fin=fopen("cast.in","r");
    int t=read();
    while(t--) tc();
    return 0;
}