#include <stdio.h>

int a[16][16], used[16], cost[16], n, st[16], sol = 200000000;

void bkt(int);

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 = 1; i <= n; ++i)
		{
			for(j = 1; j <= n; ++j)
			{
				scanf("%d", &a[i][j]);
			}
		}
		used[1] = 1;
		st[1] = 1;
		bkt(2);
		printf("%d\n", sol);
	}

	return 0;
}

void bkt(int k)
{
	if(k == n + 1)
	{
		int max = 0;
		for(int i = 1; i <= n; ++i)
		{
			if(cost[i] > max)
			{
				max = cost[i];
			}
		}
		if(sol > max)
		{
			sol = max;
		}
	}
	else
	{
		int i, j;
		for(i = 1; i <= n; ++i)
		{
			if(!used[i])
			{
				for(j = 1; j < k; ++j)
				{
					if(cost[st[j]] + a[st[j]][i] < sol)
					{
						cost[st[j]] += a[st[j]][i];
						cost[i] = cost[st[j]];
						st[k] = i;
						used[i] = 1;
						bkt(k + 1);
						cost[st[j]] -= a[st[j]][i];
						used[i] = 0;
					}
				}
			}
		}
	}
}