#include <stdio.h>

const int inf = 200000000;

int n, c[12][1 << 12], a[12][12], sol;

int f(int, int);
int max(int a, int b)
{
	if(a > b)
		return a;
	return b;
}

int main()
{
	freopen("cast.in", "r", stdin);
	freopen("cast.out" ,"w", stdout);

	int t, i, j;

	for(scanf("%d", &t); t; --t)
	{
		scanf("%d", &n);
		for(i = 0; i < n; ++i)
		{
			for(j = 0; j < (1 << n); ++j)
			{
				c[i][j] = inf;
			}
		}
		for(i = 0; i < n; ++i)
		{
			c[i][1 << i] = 0;
		}
		for(i = 0; i < n; ++i)
		{
			for(j = 0; j < n; ++j)
			{
				scanf("%d", &a[i][j]);
			}
		}
		sol = f(0, (1 << n) - 1);
		printf("%d\n", sol);
	}

	return 0;
}

int f(int nod, int conf)
{
	if(c[nod][conf] != inf)
	{
		return c[nod][conf];
	}
	else
	{
		int min = inf, i, j;
		for(i = 1; i < conf; ++i)
		{
			if(((i & conf) == i) && !((1 << nod) & i))
			{
				for(j = 0; j < n; ++j)
				{
					if((1 << j) & i)
					{
						if(min > max(f(nod, conf ^ i), f(j, i)) + a[nod][j])
						{
							min = max(c[nod][conf ^ i], c[j][i]) + a[nod][j];
						}
					}
				}
			}
		}
		c[nod][conf] = min;
		return c[nod][conf];
	}
}