#include <bits/stdc++.h>

using namespace std;
ifstream fin("cast.in");
ofstream fout("cast.out");
typedef long long ll;
ll t,n,v[24][24],dp[(1<<12)][13];
void solve()
{
    fin>>n;
    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++)
        for(int r=1;r<=n;r++)
            dp[mask][r]=1e9;
    for(int i=1;i<=n;i++)
        dp[(1<<(i-1))][i]=0;
    for(int mask=1;mask<(1<<n);mask++)
        for(int r1=1;r1<=n;r1++)
            if((mask>>(r1-1))&1)
            {
                for(int submask=(mask&(mask-1));submask;submask=((submask-1)&mask))
                {
                    if((submask>>(r1-1))&1)
                        continue;
                    int lft=(mask^submask);
                    for(int r2=1;r2<=n;r2++)
                        if((submask>>(r2-1))&1)
                            dp[mask][r1]=min(dp[mask][r1],v[r1][r2]+max(dp[lft][r1],dp[submask][r2]));
                }
            }
    fout<<dp[(1<<n)-1][1]<<'\n';
}
int main()
{
    fin>>t;
    while(t--)
        solve();
    return 0;
}