#include <iostream>
#include <fstream>
#include <map>
#include <cassert>
#include <algorithm>

using namespace std;

class State {
public:
	int covered;
	int car[3];

	State( int covered, int c1, int c2, int c3 ) : covered(covered) {
		car[0] = c1, car[1] = c2, car[2] = c3;
		sort(car, car+3);
	}

	bool operator < ( const State &s ) const {
		if ( covered < s.covered ) return true;
		if ( covered > s.covered ) return false;

		for ( int i = 0; i < 3; i++ )
			if ( car[i] < s.car[i] ) return true;
			else if ( car[i] > s.car[i] ) return false;
		return false;
	}

};

#define NLOCATION_MAX 30

int nlocation;
int D[NLOCATION_MAX][NLOCATION_MAX];

void warshall() {
	for ( int k = 0; k < nlocation; k++ )
		for ( int i = 0; i < nlocation; i++ )
			for ( int j = 0; j < nlocation; j++ )
				D[i][j] = min(D[i][j], D[i][k]+D[k][j]);
}

int compute() {
	map<State, int> S;
	multimap<int, State> M;

	State Init(0, 0, 0, 0);

	S.insert(make_pair(Init, 0));
	M.insert(make_pair(0, Init));

	while ( !M.empty() ) {
		const int d = M.begin()->first;
		State s = M.begin()->second;
		M.erase(M.begin());

		if ( S[s] < d ) continue;
		if ( s.covered == nlocation-1 ) return d;

		const int next = s.covered + 1;
		State s1(next, next, s.car[1], s.car[2]);
		const int d1 = d + D[s.car[0]][next];
		State s2(next, s.car[0], next, s.car[2]);
		const int d2 = d + D[s.car[1]][next];
		State s3(next, s.car[0], s.car[1], next);
		const int d3 = d + D[s.car[2]][next];

		if ( S.find(s1) == S.end() || S[s1] > d1 ) {
			S[s1] = d1;
			M.insert(make_pair(d1, s1));
		}
		if ( S.find(s2) == S.end() || S[s2] > d2 ) {
			S[s2] = d2;
			M.insert(make_pair(d2, s2));
		}
		if ( S.find(s3) == S.end() || S[s3] > d3 ) {
			S[s3] = d3;
			M.insert(make_pair(d3, s3));
		}
	}

	assert( false );
}

int main() {
	ifstream fin("magazine.txt");
	int ntest; fin >> ntest;

	for ( int n = 0; n < ntest; n++ ) {
		fin >> nlocation;
		for ( int i = 0; i < nlocation; i++ ) {
			D[i][i] = 0;
			for ( int j = i+1; j < nlocation; j++ ) fin >> D[i][j], D[j][i] = D[i][j];
		}

		warshall();
		const int result = compute();
		cout << result << endl;
	}

	return 0;
}