#include<fstream>
using namespace std;
int n, i, j, ii, jj, t;
int a[15][15], d[(1 << 12) + 2][13];
ifstream fin("cast.in");
ofstream fout("cast.out");
int main(){
    fin>> t;
    for(; t; t--){
        fin>> n;
        for(i = 0; i < n; i++){
            for(j = 0; j < n; j++){
                fin>> a[i][j];
            }
        }
        for(ii = 1; ii < (1 << n); ii++){
            for(i = 0; i < n; i++){
                if( ( (ii >> i) & 1) == 0){
                    continue;
                }
                if(ii == (1 << i)){
                    break;
                }
                d[ii][i] = 1000000000;
                for(jj = ii - (1 << i); jj >= 1; jj = (jj - 1) & ( ii - (1 << i) ) ){
                    for(j = 0; j < n; j++){
                        if( ( (jj >> j) & 1) == 1){
                            d[ii][i] = min(d[ii][i], a[i][j] + max(d[ii - jj][i], d[jj][j]) );
                        }
                    }
                }
            }
        }
        fout<< d[(1 << n) - 1][0] <<"\n";
    }
    return 0;
}