#include<iostream>
#include<vector>
#include<string>
#include<string.h>
#include<stdio.h>
#include<set>
#include<math.h>
#include<algorithm>
#include<iomanip>

using namespace std;

vector<vector<int> > grid;
int mem[1000][1000];
int n;

/*
int setbit(int  mask,int  idx,int  value = 1 ){ return ( value ) ? ( mask | (1<<idx) ) : ( mask &~ (1<<idx) ); }
int getbit(int  mask , int  idx ) { return ( (mask>>idx) & 1 ) == 1; }
int  cntbit( int  mask ) { int ret=0; while(mask) { if(mask%2)  ret++;  mask/=2;  }  return ret; }*/

int F(int maskR,int maskC){

    if(maskR==((1<<n)-1)&&maskC==((1<<n)-1))  return 0;

    int &x=mem[maskR][maskC];

    if(x!=-1)  return x;


    int MAX=-1000000;
    int MIN=1000000;

    for(int a=0;a<n;++a){

        if(!( maskR & (1 << a) ) ){

            //MIN=1000000;
            for(int b=0;b<n;++b){

                if(!(maskC & (1<<b) ) )
                    MIN=min(MIN,grid[a][b]+F(maskR | (1<<a) ,maskC | (1<<b) ));

            }

        }

        MAX=max(MAX,MIN);

    }

    return x=MAX;


}

int main(){

    int t,x;
    vector<int> temp;
    cin>>t;
    for(int i=0;i<t;++i){

        memset(mem,-1,sizeof mem);
        grid.clear();

        cin>>n;

        for(int a=0;a<n;++a){

            temp.clear();
            for(int b=0;b<n;++b){
                cin>>x;
                temp.push_back(x);

            }
            grid.push_back(temp);

        }

        cout<<F(0,0)<<"\n";

    }


}