在美团和饿了么大行其道的今天，囊中羞涩的小周和小美，也随大流加入了配送员的行列。每天下课后，他们都去堕落街帮北京烤鸭店送外卖。

过了好些日子，小周发现每次送外卖，小美总比自己先回来，就算自己拼命跑啊跑，也总是比她慢，明明小美也是和自己一样，走着去送外卖的（等外卖的都饿死了╮(╯﹏╰)╭）。

小周忍不住问了小美这是怎么回事，小美说：“笨蛋，本小姐每次出去都选最短的路，肯定比你走远的路快啊！”

小周恍然大悟，深恨自己怎么没有早早想到这一点，不过亡羊补牢，为时未晚，立即决定效仿小美的做法。小周将店的位置标号为0，其他要送外卖的位置标号分别是1,2,3……然后又将各个标号之间的距离做了一张二维表A，其中A[0][i]代表从店家出发到第i个外卖点的距离，A[i][j](i!=0&&j!=0)表示第i个外卖点到第j个外卖点的距离。

小周每次都从店里出发，送完所有外卖之后，就从最后一个送完外卖的地点径直地回到店里，因为直接回去总是最近的，小周统计出来的表的确也是这样的。保证矩阵对称且主对角线上的元素都是0。

不过由于小周实在是太忙了，连计算最短路线的时间都没有，现在给你这张小周做好的表，请你帮小周确定一下最短的路线吧！

第一行输入数据的组数T（1<=T<=50）。

对于每一组数据，第一行一个n（0 < n <= 9）,代表要送的外卖数量，然后一个(n+1)*(n+1)的矩阵A，代表小周的统计出来距离表，0 <= A[i][j] <= 500。

对于每组数据，输出送完所有外卖并回到店里的最短的距离

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <string>

#include <map>

#include <cmath>

#include <set>

using namespace std;

int n,Map[][],maxi;

int status[][ << ];

int DFS(int v,int S)

{

    if(S==(maxi-)) return  Map[v][];

    if(status[v][S]) return status[v][S];

    int M=;

    for(int i=; i<=n; i++)

        if(!(S&(<<(i-)))&&v!=i)

        {

            S|=(<<(i-));

            M=min(M,DFS(i,S)+Map[v][i]);

            S&=(~(<<(i-)));

        }

    return status[v][S]=M;

}

int main()

{

    //freopen("salesman.in","r",stdin);

    //freopen("salesman.out","w",stdout);

    int T;

    scanf("%d", &T);

    while(T--){

    memset(status, , sizeof(status));

    scanf("%d",&n); n++;

    maxi=(int)pow(2.0,n*1.0);

    for(int i=; i<=n; i++)

        for(int j=; j<=n; j++)

            scanf("%d",&Map[i][j]);

    cout<<DFS(,)<<endl;

    }

    return ;

}