#include<stdio.h>
#include<algorithm>
using namespace std;

#define NMAX 15
#define INF 1000000005

int n,cost[NMAX][NMAX],biti[NMAX],solutie;
int t,dinamica[1<<14][NMAX],nr_biti;

int main ()
{
	int i,j,bit,indice_vecin,vecin,indice_tata,tata,conf;
	
	freopen("cast.in","r",stdin);
	freopen("cast.out","w",stdout);
	
	scanf("%d",&t);
	
	for(; t; t--)
	{
		scanf("%d",&n);
		for(i = 1; i <= n; i++)
			for(j = 1; j <= n; j++)
				scanf("%d", &cost[i][j]);
		for(i = 1; i < (1<<n); i++)		
		{
			nr_biti = 0;
			for(bit = 1; bit <= n; bit++)
				if(i & (1 << (bit - 1)))
					biti[++nr_biti] = bit;
			//printf("Configuratia %d are biti pe:\n",i);		
			//for(bit = 1; bit <= nr_biti; bit++)
			//	printf("%d ",biti[bit]);
			//printf("\n");	
			
			if(nr_biti == 1)	
			{
				dinamica[i][biti[1]] = 0;
				continue;
			}	
					
			for(indice_tata = 1; indice_tata <= nr_biti; indice_tata++)
			{
				tata = biti[indice_tata];
				dinamica[i][tata] = INF;
			//	printf("Vreau sa calculez dinamica[%d][%d]\n{\n",i,tata);
				
				for(j = 1; j < (1 << nr_biti); j++)
				{
					conf = 0;
					for(bit = 1; bit <= nr_biti; bit++)
						if(j & (1 << (bit - 1)))
							conf += (1 << (biti[bit] - 1));
					if(conf & (1 << (tata - 1)))
						continue;		
					for(indice_vecin = 1; indice_vecin <= nr_biti; indice_vecin++)	
					{
						vecin = biti[indice_vecin];				
						if(!(conf & (1 << (vecin - 1))))
							continue;
						dinamica[i][tata] = min(dinamica[i][tata], cost[tata][vecin] + max(dinamica[i - conf][tata], dinamica[conf][vecin]));	
					}
				}
				//printf("dinamica[%d][%d] = %d\n",i,tata,dinamica[i][tata]);
			}	
		}	
//		printf("%d %d\n",dinamica[1][1],dinamica[14][4]	);	
		printf("%d\n",dinamica[(1 << n) - 1][1]);
	}
	
	return 0;
}