#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(indice_vecin = 1; indice_vecin <= nr_biti; indice_vecin++)
				{
					vecin = biti[indice_vecin];				
					if(vecin == tata)
						continue;
					solutie = INF;
					
				//	printf("	Am fixat ca ma duc in %d\n	{\n",vecin);
					
					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))) && (conf & (1 << (vecin - 1))))		
						{
						//	printf("		Iar pentru acest vecin am fixat configuratia %d\n",conf);
							solutie = min(solutie, max(dinamica[i - conf][tata], dinamica[conf][vecin]));
					//		printf("		Si solutie = %d\n",solutie);
						}	
					}
					//printf("	}\n");
					dinamica[i][tata] = min(dinamica[i][tata], solutie + cost[tata][vecin]);
				}	
				//printf("si in final da dinamica[%d][%d] = %d\n}\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;
}