#include <bits/stdc++.h>
#define inf 100000000
using namespace std;

ifstream f ("cast.in");
ofstream g ("cast.out");

int n;
int dp[15][5005];
int cost[15][15];
int test;


int main()
{
    f>>test;
    for(int t=1; t<=test; ++t)
    {
        f>>n;
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j)
                f>>cost[i][j];

        for(int i=1; i<=n; ++i)
            for(int j=0; j<(1<<n); ++j)
                dp[i][j]=inf;
        for(int i=1; i<=n; ++i)
            dp[i][(1<<(i-1))]=0;

        for(int stare=1; stare<=(1<<n)-1; ++stare)
        {
            for(int i=1; i<=n; ++i)
            {
                for(int x1=stare; x1>0; x1=(x1-1)&stare)
                {
                    for(int j=1; j<=n; ++j)
                        if(j!=i)
                        {
                            dp[i][stare]=min(dp[i][stare], max(dp[i][x1],dp[j][x1^stare])+cost[i][j]);
                        }
                }
            }
        }

        g<<dp[1][(1<<n)-1]<<"\n";
    }


    return 0;
}