#include <stdio.h>
#define minim(a, b) ((a < b) ? a : b)
#define maxim(a, b) ((a > b) ? a : b)
#define INF 2100000000

int N, COST[16][16], D[13][ (1<<13) ], st[16];
int config, rad;

int bit(int X, int nr_bit)
{ return (X & (1<<nr_bit)) != 0; }

void back(int nivel, int config2)
{
    int i;
    
    if (nivel == N)
    {
    	for (i = 0; i < N; i++)
        	if (st[i])
                D[rad][config] = minim(D[rad][config],
                		       COST[rad][i] + maxim(D[i][config2], D[rad][config-config2]));
                                    
    	return ;
    }

    st[nivel] = 0; back(nivel+1, config2);
    if (bit(config, nivel) && nivel != rad)
    { st[nivel] = 1; back(nivel+1, config2 + (1<<nivel)); }
}

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

    for (scanf("%d", &T); T; T--)
    {
    	scanf("%d", &N);
        for (i = 0; i < N; i++)
        	for (j = 0; j < N; j++)
            	scanf("%d", &COST[i][j]);

        for (config = 1; config < (1<<N); config++)
 	    for (rad = 0; rad < N; rad++)
            {
            	D[rad][config] = INF;
                if (bit(config, rad))
                {
                	if ((1<<rad) == config)
                    	D[rad][config] = 0;
                    else
		                back(0, 0);
                }
            }

        printf("%d\n", D[0][(1<<N)-1]);
    }

    return 0;
}