#include <fstream>
#include <cstring>
using namespace std ; 
const int INF = 0x3f3f3f3f;
int dp[12][1<<12] , a[12][12], Pow[12] , N; 
inline int DP(const int Root,const int Conf){
    if(dp[Root][Conf] != INF)
        return dp[Root][Conf];
    int cnt = 0;
    int i, j, k , p ,son, Son[12], bit[10],confson;
    for(i = 0;i < 12; ++i)
        if(Conf&Pow[i])
            Son[cnt++] = i;
    int MaxConfSon = Pow[cnt-2];
    for(j = 0;j < cnt; ++j){
        son = Son[j];
        if(son == Root)
            continue;
        for(i = 0,p = 0;i < cnt; ++i){
            if(Son[i] == Root || Son[i] == son)
                continue;
            bit[p++] = Son[i];
        }
        for(k = 0;k < MaxConfSon ;++k){
            confson = Pow[son];
            for(i = 0;i < cnt-2; ++i)
                if(k&Pow[i])
                    confson |= Pow[bit[i]];
            dp[Root][Conf] = min(dp[Root][Conf],a[Root][son] + max(DP(son,confson),DP(Root,Conf-confson)));
        }
    }
    return dp[Root][Conf];
}
int main(){ 
    int T ,i ,j ;
    ifstream f("cast.in");
    ofstream g("cast.out");
    Pow[0] = 1;
    for(i = 1;i < 12; ++i)
        Pow[i] = Pow[i-1] * 2;
    for( f >> T;  T; --T){
        f >> N;
        for(i = 0;i < N; ++i)
            for(j = 0;j < N; ++j)
                f >> a[i][j];
        memset(dp,INF,sizeof(dp));
        for(i = 0;i < N; ++i)
            dp[i][Pow[i]] = 0;
        g<<DP(0,(1<<N)-1)<<"\n";
    }
    g.close();
    return 0;
}