#include <bits/stdc++.h>

using namespace std;
ifstream fin("cast.in");
ofstream fout("cast.out");
typedef pair<int,int> pii;
int t,n,v[15][15];
map<pii,int> best;
int dp[(1<<12)+1];
void solve()
{
    fin>>n;
    best.clear();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            fin>>v[i][j];
    for(int mask=0;mask<(1<<n);mask++)
        best[{mask,0}]=0;
    for(int mask=1;mask<(1<<n);mask++)
    {
        for(int submask=mask;submask;submask=(submask-1)&mask)
        {
            int m1=(mask^submask);
            int m2=submask;
            int lg1=__builtin_popcount(m1);
            int lg2=__builtin_popcount(m2);
            if(lg1<lg2)
                continue;
            vector<int> b1,b2;
            for(int bit=0;bit<n;bit++)
            {
                if((m1>>bit)&1)
                    b1.push_back(bit);
                if((m2>>bit)&1)
                    b2.push_back(bit);
            }
            best[{m1,m2}]=2e9;
            for(int a:b1)
                for(int b:b2)
                {
                    int mm1=(m1-(1<<a));
                    int mm2=(m2-(1<<b));
                    int x=best[{mm1,mm2}];
                    int cost=max(x,v[a+1][b+1]);
                    best[{m1,m2}]=min(best[{m1,m2}],cost);
                }
        }
    }
    for(int mask=0;mask<(1<<n);mask++)
        dp[mask]=1e9;
    dp[1]=0;
    for(int mask=2;mask<(1<<n);mask++)
    {
        if(mask%2==0)
            continue;
        for(int submask=mask;submask;submask=(submask-1)&mask)
        {
            int m1=(mask^submask);
            int m2=submask;
            int lg1=__builtin_popcount(m1);
            int lg2=__builtin_popcount(m2);
            if(lg1<lg2)
                continue;
            if(best.count({m1,m2})!=0)
                dp[mask]=min(dp[mask],dp[m1]+best[{m1,m2}]);
        }
    }
    fout<<dp[(1<<n)-1]<<'\n';
}
int main()
{
    fin>>t;
    while(t--)
        solve();
    return 0;
}