#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define MIN_VALUE 1415.0000000000


double min_distance = MIN_VALUE;
double total_distance = 0.0f;
unsigned int number_of_city = 0;
vector<double> pre_distance;

int checking(int i , int j)
{
    int ret = 0;
    if(i <= number_of_city && j <= number_of_city)
    {
        ret = 1;
    }
    return ret;
}
void init(vector<int>& number, int l)
{
    number.clear();
    pre_distance.clear();
    total_distance = 0.0f;
    min_distance = MIN_VALUE;
    for(int i = 0; i < number_of_city; i++)
    {
        number.push_back(i);
    }

    vector<int>::iterator iter = number.begin();
    for(;iter != number.end();++iter)
    {
        if(*iter == l)
        {
            number.erase(iter);
            break;
        }
    }
    return;
}

int erase(vector<int>& number, int from)
{
    int ret = 0;
    if(number.size() == 1)
    {
        return ret + 1;
    }

    vector<int>::iterator iter = number.begin();
    for(;iter != number.end();++iter)
    {
        if(*iter == from)
        {
            number.erase(iter);
            break;
        }
    }

    return ret;
}

int spot_isPromising(vector<int>& number, int j)
{
    int ret = 0;
    vector<int>::iterator iter2 = number.begin();
    for(; iter2 != number.end(); ++iter2)
    {
        if(j == *iter2)
        {
            ret = 1;
            break;
        }
        else
        {
            ret = 0;
        }
    }
    return ret;
}

int isPromising(vector<vector<double>>& city, int i, int j, vector<int>& number)
{
    int ret = 1;

    vector<double>::iterator iter = pre_distance.begin();

    for(; iter != pre_distance.end(); ++iter)
    {
        if(pre_distance.size() > 6)
        {
            break;
        }
        if(checking(i,j) == 0)
        {
            break;
        }
        if(*iter == city[i][j])
        {
            ret = 0;
            break;
        }
    }

    ret = spot_isPromising(number, j);
    return ret;
}

double minimum_distance(vector<vector<double>>& city, int from, vector<int>& number)
{
    int ret_val = 1;
    int i = from;
    static int next = 0;
    if(erase(number, i))
    {
        return total_distance;
    }
    else
    {
        for(int j = 0; j < city.size(); j++)
        {
            if(checking(i,j) == 0)
            {
                break;
            }
            if(i == j && city[i][j]  == 0)
            {
                continue;
            }
            if(i == j != 0)
            {
                ret_val = 0;
                break;
            }
            if(min_distance > city[i][j])
            {
                if(isPromising(city, i, j, number) == 0)
                {
                    continue;
                }
                min_distance = city[i][j];
                next = j;
            }
            if(min_distance == MIN_VALUE)
            {
                min_distance = city[i][j];
                next = j;
            }
        }
        pre_distance.push_back(min_distance);
        total_distance += min_distance;
        if(!ret_val)
        {
            return ret_val;
        }
        min_distance = MIN_VALUE;
        return minimum_distance(city, next, number);
    }
}

void clearing(vector<double>& temp, vector<int>& number)
{
    temp.clear();
    number.clear();
    return;
}

int main()
{
    cout<<fixed;
    cout.precision(10);
    int loop;
    vector<double> output;
    vector<double> temp;
    vector<int> number;
    cin >> loop;

    if(loop > 50 || loop <= 0 )
    {
        return 0;
    }
    for(int i = 0; i < loop ; i++)
    {
        cin >> number_of_city;
        if(number_of_city < 3 || number_of_city > 8)
        {
            return 0;
        }
        vector<vector<double>>city(number_of_city, vector<double>(number_of_city, 0));

        for(int j = 0; j < number_of_city; j++)
        {
            for(int k = 0; k < number_of_city; k++)
            {
                cin >> city[j][k];
                if(city[j][k] < 0 || city[j][k] > MIN_VALUE)
                {
                    return 0;
                }
            }
            cout<<endl;
        }
        for(int l = 0; l < number_of_city; l++)
        {
            init(number, l);
            temp.push_back(minimum_distance(city, l, number));
        }
        output.push_back(*min_element(temp.begin(), temp.end()));
        clearing(temp, number);
    }

    vector<double>::iterator iter = output.begin();
    for(; iter != output.end(); ++iter)
    {
        cout<<*iter<<endl;
    }
    return 0;
}