#include <bits/stdc++.h>
using namespace std;
ifstream f("cast.in");
ofstream g("cast.out");
int i,j,K,bit,t,n,cost[15][15],dp[1<<12][13];
int main()
{
    f>>t;
    while(t--)
    {
        f>>n;
        for(i=0;i<n;++i)
            for(j=0;j<n;++j) f>>cost[i][j];
        for(K=1;K<(1<<n);++K)
        for(i=0;i<n;++i)
        if(K&(1<<i))
        {
            if(K==(1<<i))
            {
                dp[K][i]=0;
                continue;
            }
            dp[K][i]=(1<<30);
            for(bit=K^(1<<i);bit;bit=(bit-1)&(K^(1<<i)))
            for(j=0;j<n;++j)
            if(bit&(1<<j))
                dp[K][i]=min(dp[K][i],cost[i][j]+max(dp[K^bit][i],dp[bit][j]));
        }
        g<<dp[K-1][0]<<'\n';
    }
    return 0;
}