#include <fstream>
#define DIM 12
#define INF 1e9

using namespace std;

ifstream f("cast.in");
ofstream g("cast.out");

int n, T, dp[(1 << DIM) + 2][DIM + 2], cost[DIM + 2][DIM + 2], unu, doi;

void back(int niv){
    for(int i = 0; i < 3; ++ i){
        if(i == 1)
            unu += (1<<niv);
        if(i == 2)
            doi += (1<<niv);
        int comb = (unu | doi);
        if(dp[comb][unu] == 0 || dp[comb][doi] == 0 || comb == 0){
            if(i == 1)
                unu -= (1 << i);
            if(i == 2)
                doi -= (1 << i);
            continue;
        }
        for(int i = 0; i <= niv; ++ i){
            if((unu >> i) & 1){
                for(int j = 0; j <= niv; ++ j){
                    if((doi >> j) & 1){
                        dp[comb][i] = min(dp[comb][i], max(dp[unu][i], dp[doi][j]) + cost[i][j]);
                        dp[comb][j] = min(dp[comb][j], max(dp[unu][i], dp[doi][j]) + cost[j][i]);
                    }
                }
            }
        }
        if(niv < n - 1)
            back(niv + 1);

        if(i == 1)
            unu -= (1 << i);
        if(i == 2)
            doi -= (1 << i);

    }

}

int main()
{
    f>>T;
    for(int t = 1; t <= T; ++ t){
        f>>n;
        int lg = (1<<n) - 1;
        for(int i = 1; i <= lg; ++ i)
            for(int j = 0; j < n; ++ j)
                dp[i][j] = INF;
        for(int i = 0; i < n; ++ i)
            dp[(1 << i)][i] = 0;
        for(int i = 1; i <= n; ++ i)
            for(int j = 1; j <= n; ++ j)
                f>>cost[i][j];
        back(0);
        g<<dp[lg][0]<<'\n';
    }
    return 0;
}