#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 order[NMAX];
ll testcaseTime;
bool flag=0;

ll Time(){
    return chrono::steady_clock::now().time_since_epoch().count();
}
int uniform_rand(int l, int r){
    mt19937 gen(Time());
    uniform_int_distribution <int> rnd(l,r);
    return rnd(gen);
}
bool visited[NMAX];
int p[NMAX],t[NMAX],b[NMAX][NMAX],n,answer=1e6;
void bkt(int pos){
    if(pos==n){
        int tmp=0;
        for(int i=0;i<n;i++)
            tmp=max(tmp,t[i]);
        answer=tmp;
        return;
    }
    if(!flag && Time()-testcaseTime>3.8e8)
        flag=1;
    if(flag) return;

    for(int i=1;i<n;i++){
        if(!visited[i]){
            visited[i]=1,p[pos]=i;
            int from=0;
            for(int j=0;j<pos;j++){
                if(t[j]+b[p[j]][i]<t[pos])
                    t[pos]=t[j]+b[p[j]][i],from=j;
            }

            if(t[pos]<answer){
                t[from]+=b[p[from]][i];
                p[pos]=i;
                bkt(pos+1);
                t[from]-=b[p[from]][i];
            }
            visited[i]=0,t[pos]=1e6;

        }
    }
}
void tc(){
    testcaseTime=Time(),flag=0,answer=1e6;
    n=read();
    for(int i=0;i<n;i++)
        order[i]=i,t[i]=1e6,visited[i]=0;
    p[0]=t[0]=0,visited[0]=1;
    for(int i=2;i<n;i++){
        swap(order[i],order[uniform_rand(1,i)]);
    }
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) b[order[i]][order[j]]=read();
    bkt(1);
    fout<<answer<<'\n';
}
int main(){
    fin=fopen("cast.in","r");
    int t=read();
    while(t--) tc();
    return 0;
}