#include <iostream>
 
using namespace std;
 
double dis[8][8];		//도시 사이의 거리
bool check[8];			//이미 지나간 도시
int N;					//도시의 수
double result;			//결과값
 
//start: 시작하는 도시, cnt: 거쳐간 도시의 수, sum: 지나온 거리
void solution(int start, int cnt, double sum)
{
	if (cnt == N - 1)			//도시를 전부 지났을 때
	{
		if (result > sum)		//기존의 결과값에 비해 지나온 거리가 짧을 때
			result = sum;
		return;
	}
 
	for (int i = 0; i < N; i++)
	{
		if (start != i && !check[i])
		{
			check[i] = check[start] = true;					//지나온 도시를 생략
			solution(i, cnt + 1, sum + dis[start][i]);
			check[i] = check[start] = false;				//새로운 경로 탐색을 위해
		}
	}
}
 
int main(void)
{
	//소수점 10자리 출력
	cout << fixed;
	cout.precision(10);
 
	int C;
	cin >> C;
 
	while (C--)
	{
		cin >> N;
 
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> dis[i][j];
				result += dis[i][j];
			}
		}
		for (int i = 0; i < N; i++)
			solution(i, 0, 0);
		cout << result << endl;
	}
}

I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmRvdWJsZSBkaXNbOF1bOF07CQkvL+uPhOyLnCDsgqzsnbTsnZgg6rGw66asCmJvb2wgY2hlY2tbOF07CQkJLy/snbTrr7gg7KeA64KY6rCEIOuPhOyLnAppbnQgTjsJCQkJCS8v64+E7Iuc7J2YIOyImApkb3VibGUgcmVzdWx0OwkJCS8v6rKw6rO86rCSCgovL3N0YXJ0OiDsi5zsnpHtlZjripQg64+E7IucLCBjbnQ6IOqxsOyzkOqwhCDrj4Tsi5zsnZgg7IiYLCBzdW06IOyngOuCmOyYqCDqsbDrpqwKdm9pZCBzb2x1dGlvbihpbnQgc3RhcnQsIGludCBjbnQsIGRvdWJsZSBzdW0pCnsKCWlmIChjbnQgPT0gTiAtIDEpCQkJLy/rj4Tsi5zrpbwg7KCE67aAIOyngOuCrOydhCDrlYwKCXsKCQlpZiAocmVzdWx0ID4gc3VtKQkJLy/quLDsobTsnZgg6rKw6rO86rCS7JeQIOu5hO2VtCDsp4DrgpjsmKgg6rGw66as6rCAIOynp+ydhCDrlYwKCQkJcmVzdWx0ID0gc3VtOwoJCXJldHVybjsKCX0KCglmb3IgKGludCBpID0gMDsgaSA8IE47IGkrKykKCXsKCQlpZiAoc3RhcnQgIT0gaSAmJiAhY2hlY2tbaV0pCgkJewoJCQljaGVja1tpXSA9IGNoZWNrW3N0YXJ0XSA9IHRydWU7CQkJCQkvL+yngOuCmOyYqCDrj4Tsi5zrpbwg7IOd6561CgkJCXNvbHV0aW9uKGksIGNudCArIDEsIHN1bSArIGRpc1tzdGFydF1baV0pOwoJCQljaGVja1tpXSA9IGNoZWNrW3N0YXJ0XSA9IGZhbHNlOwkJCQkvL+yDiOuhnOyatCDqsr3roZwg7YOQ7IOJ7J2EIOychO2VtAoJCX0KCX0KfQoKaW50IG1haW4odm9pZCkKewoJLy/shozsiJjsoJAgMTDsnpDrpqwg7Lac66ClCgljb3V0IDw8IGZpeGVkOwoJY291dC5wcmVjaXNpb24oMTApOwoKCWludCBDOwoJY2luID4+IEM7CgkKCXdoaWxlIChDLS0pCgl7CgkJY2luID4+IE47CgoJCWZvciAoaW50IGkgPSAwOyBpIDwgTjsgaSsrKQoJCXsKCQkJZm9yIChpbnQgaiA9IDA7IGogPCBOOyBqKyspCgkJCXsKCQkJCWNpbiA+PiBkaXNbaV1bal07CgkJCQlyZXN1bHQgKz0gZGlzW2ldW2pdOwoJCQl9CgkJfQoJCWZvciAoaW50IGkgPSAwOyBpIDwgTjsgaSsrKQoJCQlzb2x1dGlvbihpLCAwLCAwKTsKCQljb3V0IDw8IHJlc3VsdCA8PCBlbmRsOwoJfQp9

MgozCjAuMDAwMDAwMDAwMCAgNjExLjYxNTcyMjUyMDEgIDY0OC43NTAwNjE3Mjg5CjYxMS42MTU3MjI1MjAxICAwLjAwMDAwMDAwMDAgIDc0My44NTU3OTY3NTAxCjY0OC43NTAwNjE3Mjg5ICA3NDMuODU1Nzk2NzUwMSAgMC4wMDAwMDAwMDAwCjQKMC4wMDAwMDAwMDAwICAzMjYuMDAwODk5NDU4NiAgNTAzLjEwNjYwNzYwNzcgIDI5MC4wMjUwOTIyOTk4CjMyNi4wMDA4OTk0NTg2ICAwLjAwMDAwMDAwMDAgIDIyNS4xNzg1NzI4NDM2ICAzOTUuNDAxOTM2NzM4NAo1MDMuMTA2NjA3NjA3NyAgMjI1LjE3ODU3Mjg0MzYgIDAuMDAwMDAwMDAwMCAgNjIwLjM5NDU1MjA2MzIKMjkwLjAyNTA5MjI5OTggIDM5NS40MDE5MzY3Mzg0ICA2MjAuMzk0NTUyMDYzMiAgMC4wMDAwMDAwMDAw

2
3
0.0000000000  611.6157225201  648.7500617289
611.6157225201  0.0000000000  743.8557967501
648.7500617289  743.8557967501  0.0000000000
4
0.0000000000  326.0008994586  503.1066076077  290.0250922998
326.0008994586  0.0000000000  225.1785728436  395.4019367384
503.1066076077  225.1785728436  0.0000000000  620.3945520632
290.0250922998  395.4019367384  620.3945520632  0.0000000000