#include <stdio.h>

#define MAXCITY 8

double matrix[MAXCITY][MAXCITY];
int isSelected[MAXCITY];
int numOfCity;

int isAllSelected()
{
    int i;

    for(i=0;i<numOfCity;i++)
        if(isSelected[i] == 0 )
            return 0;

    return 1;
}

double travel(int prevCity)
{
    int i;
    double distance;
    double minDist =9999.0;
    int minCity;

    if(isAllSelected())
        return 0.0;

    for(i=0; i<numOfCity; i++)
    {
        if(isSelected[i]== 0) {
            isSelected[i] = 1;

            distance = travel(i);

            if( (distance < minDist) )
            {
                minDist = distance;
                minCity = i;
            }


            isSelected[i] = 0;
        }

    }

    if( prevCity != -1) {
        minDist += matrix[prevCity][minCity];
        //printf("minCity = %d\n",minCity);
    }



    return minDist;
}

int main()
{
    int cases;

    int i,j;
    double inputd;
    double minDist;

    //freopen("input.txt","r",stdin);
    scanf("%d",&cases);

    while(cases--) {
        scanf("%d",&numOfCity);

        for(i=0; i<numOfCity; i++)
        {
            for(j=0; j<numOfCity;j++)
            {
                scanf("%lf",&inputd);
                matrix[i][j] = inputd;
                //printf("%.10f ",matrix[i][j]);

            }
            //printf("\n");
        }

        for(i=0; i<MAXCITY; i++)
            isSelected[i] = 0;

        minDist = travel(-1);
        printf("%.10lf\n", minDist);

    }

    return 0;
}