#include <iostream>

using namespace std;

double abc[10][10];
double MIN=999999;

void swap(int* arr, int i, int j){
    int temp  = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void perm(int* arr, int depth, int n){
    if(depth == n){
        /*for(int i=0; i<n; i++){
            cout<<arr[i]<<" ";
        }cout<<endl;*/
        //한턴에 다음것을 가지고 좌표를 찾아 값을 넣는다.
        double sum=0;
        for(int i=0; i<n-1; i++){
            double temp = abc[arr[i]][arr[i+1]];
            sum+=temp;
            if(sum > MIN) return;
        }
        if(MIN > sum) MIN = sum;
        return;
    }
    for(int i=depth; i<n; i++){
        swap(arr, i, depth);
        perm(arr, depth+1, n);
        swap(arr, i ,depth);
    }
}


int main(int argc, char** argv)
{
    int test_case;
    int T;

    int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7};
    cin >> T;
    for(test_case = 0; test_case < T; test_case++)
    {
        int n;
        cin>>n;

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin>>abc[i][j];
            }
        }

        perm(arr, 0, n);
        printf("%.10lf\n", MIN);
    }
    return 0;
}