#include <iostream>
#include<string>
#include <string.h>
#include <cstdlib>


using namespace std;

void CheckPath(int Current,int CurrentPath, int PassedPath[8], double ThisPathTotal);

 int Path;
 double TotalDistance;
 double DistancePath[8][8] = { { 0 } };

int main()
{
    int Count;
    cin >> Count;
    while (Count--)
    {
    //제일 처음 총 거리를 0으로 초기화
        TotalDistance = 0;

        //순서대로 몇번으로 가는지 배열에 차례로 쌓이는데 최대 길은 8까지만이니 없는 경우인 10으로 초기화
        int PassedPath[8] = { 10, 10, 10, 10, 10, 10, 10, 10 };

        cin >> Path;

        //for문을 이용하여 값을 받고
        for (int i = 0; i < Path; i++)
        {
            for (int j = 0; j < Path; j++)
            { 
                cin >> DistancePath[i][j];
            }
        }

        //출발점을 다르게 하여 함수 호출
        for (int i = 0; i < Path; i++)
        {
            PassedPath[0] = i;
            CheckPath(0,i,PassedPath,0);
        }


        printf("%.10f\n", TotalDistance);



    }
}

void CheckPath(int Current, int CurrentPath, int PassedPath[8],  double ThisPathTotal)
{
    Current += 1;

    //Current는 지금까지 간 길의 수인데 이게 해당만큼 가게 되면지금 저장되어있는 총 길이를 비교함
    if (Current == Path)
    {
        if (TotalDistance!=0 && TotalDistance > ThisPathTotal)
            TotalDistance = ThisPathTotal;

        for (int i = 1; i < 8; i++)
        {
            //지금까지 지나온 길을 다시 초기화
            PassedPath[i] = 10;
        }

        return;

    }

    //모든 길을 다 간게 아니라면
    else
    {
    //for문을 이용해 PassedPath(지나간길)안에 없는 길을 다 가본다
        for (int i = 0; i < Path; i++)
        {
            if (i != PassedPath[0] && i != PassedPath[1] && i != PassedPath[2] && i != PassedPath[3] && 
                i != PassedPath[4] && i != PassedPath[5] && i != PassedPath[6] && i != PassedPath[7])
            {
                //안 가본 길이있다면 갈 길을 이길로 지정
                PassedPath[Current] = i;

                //다음 길을 어디로 갈지 경우의수 조사
                CheckPath(Current, i, PassedPath, ThisPathTotal += DistancePath[CurrentPath][i]);
            }
        }
    }
}