#include <iostream>
#include <fstream>
#define MAXN 12
#define INF 2000000000
using namespace std;
ifstream si("cast.in");
ofstream so("cast.out");
int v[MAXN][MAXN];
int dp[MAXN][(1<<MAXN)];
int main()
{
    int q;
    si>>q;
    while(q--)
    {
        int n;
        si>>n;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                si>>v[i][j];
        for(int i=0;i<n;i++)
            for(int j=0;j<(1<<n);j++)
                dp[i][j]=INF;
        for(int i=0;i<n;i++)
            dp[i][1<<i]=0;
        for(int c=1;c<(1<<n);c++)
            for(int i=0;i<n;i++)
            {
                if(c&(1<<i)); else continue;
                int conf=c^(1<<i);
                for(int c2=conf;c2;c2=(c2-1)&conf)
                    for(int j=0;j<n;j++)
                    {
                        if(!(c2&(1<<j)))
                            continue;
                        dp[i][c]=min(dp[i][c],v[i][j]+max(dp[i][c^c2],dp[j][c2]));
                    }
            }
        so<<dp[0][(1<<n)-1]<<'\n';
    }
    return 0;
}