#include<fstream>
#include<vector>
#define INF 999999999
using namespace std;
ifstream f("cast.in");
ofstream g("cast.out");
int t,n,i,j,d[13][10000],a[13][13];
inline int rez(int ul,int  conf)
{
    if(d[ul][conf]!=INF)
    {
        return d[ul][conf];
    }
    vector<int>v;
    for(int i=0;i<n;++i)
    {
        if((conf&(1<<i))&&i!=ul)
        v.push_back(i);
    }
    for(int i=0;i<(1<<v.size());++i)
    {
        int val=0;
        for(int j=0;j<v.size();++j)
        if(i&(1<<j))
        val|=(1<<v[j]);
        for(int j=0;j<v.size();++j)
        if(i&(1<<j))
        d[ul][conf]=min(d[ul][conf],max(a[ul][v[j]]+rez(v[j],val),a[ul][v[j]]+rez(ul,conf^val)));
    }
    return d[ul][conf];
}
int main()
{
    for(f>>t;t;--t)
    {
        f>>n;
        for(i=0;i<n;++i)
        {
            for(j=0;j<n;++j)
            f>>a[i][j];
            for(j=0;j<(1<<n);++j)
            d[i][j]=INF;
            d[i][1<<i]=0;
        }
        g<<rez(0,(1<<n)-1)<<'\n';
    }
    return 0;
}