#include <iostream>
#include <fstream>
#include <vector>
#define DN 5
#define MULT (1<<30)
using namespace std;

int t, n, lg[DN][DN], bst[DN][1<<DN];

int Memo(int s, int state)
{
    if(bst[s][state]!=MULT)
        return bst[s][state];

    vector<int> v;

    for(int i=0; i<n; ++i)
        if((state&(1<<i)) && i!=s) v.push_back(i);
    for(int i=0; i<(1<<v.size()); ++i)
    {
        int sm=0;
        for(int j=0; j<v.size(); ++j)
            if(i&(1<<j)) sm|=(1<<v[j]);
        for(int j=0; j<v.size(); ++j)
            if(i&(1<<j))

        bst[s][state]=min(bst[s][state],max(lg[s][v[j]]+Memo(v[j],sm),lg[s][v[j]]+Memo(s,state^sm)));
    }

    return bst[s][state];
}

int main()
{
    ifstream f("cast.in");
    ofstream g("cast.out");
    for(f>>t;t;--t)
    {
        f>>n;

        for(int i=0; i<n; ++i)
        {
            for(int j=0; j<n; ++j)
                f>>lg[i][j];
            for(int j=0; j<(1<<n); ++j)
                bst[i][j]=MULT;

            bst[i][1<<i]=0;
        }

        g<<Memo(0,(1<<n)-1)<<'\n';
    }

    f.close(); g.close();
    return 0;
}