using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <algorithm>

#define pb push_back
#define sz size
#define f first
#define s second
#define II inline
#define ll long long
#define db double
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define CC(v) memset((v),0,sizeof((v)))
#define CP(v,w) memcpy((v),(w),sizeof((w)))
#define mp make_pair

#define IN "cast.in"
#define OUT "cast.out"
#define oo 51400

typedef vector<int> VI;
typedef pair<int,int> pi;
typedef vector<string> VS;

int N,T;
int D[16][16];
char Bit[1<<12];
unsigned short int C[16][1<<12];

II int getbit(int x)  
{  
    int bt(0);  
    for(;x;bt += (x&1),x >>= 1);  
    return bt;  
} 

II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%d",&T);
	
	FOR(i,0,(1<<12)-1)
		Bit[i] = getbit(i);
}

II void solve()
{
	int stv[16],C[16];
	bool viz[16];
	int rez(1<<20);
	
	scanf("%d",&N);
	FOR(i,1,N)
	FOR(j,1,N)
		scanf("%d",&D[i][j]);
	
	FOR(k,1,500000)
	{
		CC(viz);
		stv[0] = stv[1] = 1;
		viz[1] = true;
		CC(C);
		
		FOR(i,1,N-1)
		{
			int y,x = stv[ rand() % stv[0] + 1 ];
			for(y = rand() % N + 1;viz[y];y = rand() % N + 1);
			
			C[x] += D[x][y];
			stv[++stv[0]] = y;
			viz[y] = true;
		}	
		
		int sum = 0;
		FOR(i,1,N)
			sum = max(sum,C[i]);
		if(rez==1)
			break;
		rez = min(rez,sum);	
	}	
	
	printf("%d\n",rez);
}

int main()
{
	scan();
	srand((int)time(0));
	FOR(i,1,T)
		solve();
	return 0;
}