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

#define NMAX 13
#define INF 1000000005

int n,cost[NMAX][NMAX],biti[NMAX],solutie;
int t,dinamica[1<<13][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;
			if(nr_biti == 1)	
			{
				dinamica[i][biti[1]] = 0;
				continue;
			}	
					
			for(indice_tata = 1; indice_tata <= nr_biti; indice_tata++)
			{
				tata = biti[indice_tata];
				if((i&1) && tata != 1)
					continue;
					
				dinamica[i][tata] = INF;
				for(j = 1; j < (1 << nr_biti); j++)
				{
					if(j & (1 << (indice_tata - 1)))
						continue;
						
					conf = 0;
					for(bit = 1; bit <= nr_biti; bit++)
						if(j & (1 << (bit - 1)))
							conf += (1 << (biti[bit] - 1));
							
					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("%d\n",dinamica[(1 << n) - 1][1]);
	}
	
	return 0;
}