#include <stdio.h>
#include <string.h>
#define NMAX 14
#define SHIFTN (1<<NMAX)
#define INFI 0x3f3f3f3f
int n;
int cost[NMAX][NMAX];
int min[NMAX][SHIFTN];
short uz[NMAX][SHIFTN];
//short nrbit[SHIFTN];
void read()
{
int i, j;
scanf("%d", &n);
for(i = 1; i <= n; ++i)
for(j = 1; j <= n; ++j)
scanf("%d", &cost[i][j]);
}
inline int MIN(int a, int b)
{
return (a < b) ? (a) : (b);
}
inline int MAX(int a, int b)
{
return (a > b) ? (a) : (b);
}
int solve(int x, int conf)
{
if(uz[x][conf])
return min[x][conf];
if(nrbit[conf] == 1)
return (min[x][conf] = 0);
//printf("\n");
//printf("%d %d\n", x, conf);
++uz[x][conf];
int others = conf - (1<<(x-1));
int i, j;
for(i = 1; i < (1<<n); ++i)
{
if((i & others) == i)
{
//printf("mere %d\n", i);
for(j = 1; j <= n; ++j)
{
if(((i & (1 << (j-1))) > 0))
{
//printf("incerc cu %d\n", j);
min[x][conf] = MIN(min[x][conf], cost[x][j] + MAX(solve(j, i), solve(x, conf ^ i)));
//printf("x = %d, conf = %d, others = %d, i = %d, j = %d\n", x, conf, others, i, j);
//printf("%d\n", conf-i);
//printf("solve(j, i) = %d, solve(x, conf-i) = %d\n", solve(j, i), solve(x, conf-i));
//printf("\n");
}
}
}
}
return min[x][conf];
}
int main()
{
freopen("cast.in", "r", stdin);
freopen("cast.out", "w", stdout);
int t;
scanf("%d", &t);
//for(int i = 1; i < SHIFTN; ++i)
// nrbit[i] = nrbit[i>>1] + (i&1);//, printf("%d %d\n", i, nrbit[i]);
while(t--)
{
read();
memset(uz, 0, sizeof(uz));
memset(min, INFI, sizeof(uz));
printf("%d\n", solve(1, (1<<n)-1));
//for(int i = 1; i <= n; ++i)
//{
// for(int j = 1; j < (1<<n); ++j)
// printf("%d ", min[i][j]);
// printf("\n");
//}
}
return 0;
}