#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, put[(1<<DIM) + 10];

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);
        for(int ii = 0; ii <= niv; ++ ii){
            if((unu >> ii) & 1){
                for(int j = 0; j <= niv; ++ j){
                    if((doi >> j) & 1){
                        dp[comb][ii] = min(dp[comb][ii], max(dp[unu][ii], dp[doi][j]) + cost[ii][j]);
                        dp[comb][j] = min(dp[comb][j], max(dp[unu][ii], dp[doi][j]) + cost[j][ii]);
                    }
                }
            }
        }

        if(niv < n - 1)
            back(niv + 1);

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

    }

}

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 = 0; i < n; ++ i)
            for(int j = 0; j < n; ++ j)
                f>>cost[i][j];
        back(0);
        g<<dp[lg][0]<<'\n';
    }
    return 0;
}