#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("cast.in");
ofstream cout("cast.out");

int cost[15][15];

int d[15][50000];

int main() {
    int t;
    cin>>t;
    while (t) {
        --t;
        int n;
        cin>>n;
        for (int i = 1; i<= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                cin>>cost[i][j];
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= (1 << n) - 1; ++j) {
                d[i][j] = 2000000000;
            }
             d[i][1 << (i - 1)] = 0;
        }
        for (int i = 1; i <= (1 << n) - 1; ++i) {
            for (int j = 1; j <= n; ++j) {
                if ((1 << (j - 1)) & i) {
                    for (int k = i ^ (1 << (j - 1)); k; k = (k - 1) & (i - (1 << (j - 1))))  {
                        for (int l = 1; l <= n; ++l) {
                            d[j][i] = min(d[j][i], cost[j][l] + max(d[j][i ^ k], d[l][k]));
                        }
                    }
                }
            }
        }
        cout<<d[1][(1 << n )- 1]<<"\n";
    }
    return 0;
}