#include <cstdio>
#include <algorithm>
#include <cstring>

#define NMAX 17
#define INF 0x3f3f3f3f

using namespace std;

int a[NMAX][NMAX], Dp[NMAX][1 << NMAX];
int n, T;

int memo(int x, int Conf){
    if(Dp[x][Conf] != INF)
        return Dp[x][Conf];
    int Ans = Dp[x][Conf];
    if(! (Conf & (Conf - 1))){
        for(int i = 0; i < n; ++i)
            if(Conf & (1 << i))
                return a[x][i];
        return Ans;
    }
    for(int i = 0; i < n; ++i)
        if(Conf & (1 << i)){
            int New_Conf = Conf ^ (1 << i);
            Ans = min(Ans, a[x][i] + memo(x, New_Conf));
            Ans = min(Ans, a[x][i] + memo(i, New_Conf));
            for(int y = (New_Conf & (New_Conf - 1)); y != 0; y = (y - 1) & New_Conf)
                Ans = min(Ans, a[x][i] + max(memo(x, y), memo(i, New_Conf ^ y)));
        }
    return Ans;
}

int main(){
    freopen("cast.in", "r", stdin);
    freopen("cast.out", "w", stdout);
    scanf("%d", &T);
    while(T){
        --T;
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                scanf("%d", &a[i][j]);
        memset(Dp, INF, sizeof(Dp));
        printf("%d\n", memo(0, (((1 << n) - 1) ^ 1)));
    }
    return 0;
}