using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <algorithm>

#define pb push_back
#define sz size
#define f first
#define s second
#define II inline
#define ll long long
#define db double
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define CC(v) memset((v),0,sizeof((v)))
#define CP(v,w) memcpy((v),(w),sizeof((w)))
#define mp make_pair

#define IN "cast.in"
#define OUT "cast.out"
#define oo 51400
#define bit(x) (1<<(x-1))

typedef vector<int> VI;
typedef pair<int,int> pi;
typedef vector<string> VS;

int N,T;
int D[16][16];
char Bit[1<<12];
int C[16][1<<12];

II int getbit(int x)  
{  
    int bt(0);  
    for(;x;bt += (x&1),x >>= 1);  
    return bt;  
} 

II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%d",&T);
}

II bool comp(const int x,const int y)
{
	return getbit(x) < getbit(y);
}

II void solve()
{
	int Q[1<<12],Q1[1<<12];
	
	scanf("%d",&N);
	FOR(i,1,N)
	FOR(j,1,N)
		scanf("%d",&D[i][j]);
	
	memset(C,100,sizeof(C));	
	FOR(i,1,N)
		C[i][ bit(i) ] = 0;
	
	Q1[0] = 0;
	FOR(i,1,(1<<N)-1)
		if(getbit(i) ^ 1)
			Q1[++Q1[0]] = i;
	sort(Q1+1,Q1+Q1[0]+1,comp);
	
	FOR(ti,1,2)
	FOR(i1,1,N)
	FOR(j1,1,Q1[0])
	{
		int k1 = Q1[j1];
		if(!(bit(i1) & k1))
			continue;
		Q[Q[0]=1] = 0;
		
		FOR(i2,1,N)
		{
			if(!(k1 & bit(i2)) || i2==i1)
				continue;
			int size = Q[0];
			FOR(j2,1,size)
				Q[++Q[0]] = Q[j2] + bit(i2);
		}
		
		FOR(j2,2,Q[0])
		FOR(i2,1,N)
		{
			int k2 = Q[j2];
			if(!(k2 & bit(i2) ))
				continue;				
			C[i1][k1] = min(C[i1][k1], max(C[i1][k1 ^ k2],C[i2][k2]) + D[i1][i2]);
		}
	}	
	
	printf("%d\n",C[1][ (1<<N)-1]);
}

int main()
{
	scan();
	srand((int)time(0));
	FOR(i,1,T)
		solve();
	return 0;
}