//WellProject

#include <iostream>

using namespace std;
const int MAXN = 105;

int T, N, result, inputArr[MAXN][MAXN];
int maTranCanh[MAXN * MAXN][3], indMaTranCanh, parent[MAXN], rankk[MAXN];


void formatData() {
	result = 0;
	indMaTranCanh = 0;
	for (int i = 0; i < N; i++) {//make_set
		parent[i] = i;
		rankk[i] = 0;
	}
}

int findSet(int x) {
	if (x != parent[x]) {
		parent[x] = findSet(parent[x]);
	}
	return parent[x];
}

void jointSet(int x, int y) {
	int px = findSet(x);
	int py = findSet(y);

	if (rankk[px] > rankk[py]) {
		parent[py] = px;
	}
	else {
		parent[px] = py;
		if (rankk[px] == rankk[py]) {
			rankk[py]++;
		}
	}
}

void quickSort(int left, int right) {
	int mid = maTranCanh[(left + right) / 2][2];
	int i = left, j = right;
	while (i < right || left < j) {
		while (maTranCanh[i][2] < mid) i++;
		while (maTranCanh[j][2] > mid) j--;
		if (i <= j) {
			int temp = maTranCanh[i][2];
			maTranCanh[i][2] = maTranCanh[j][2];
			maTranCanh[j][2] = temp;

			temp = maTranCanh[i][1];
			maTranCanh[i][1] = maTranCanh[j][1];
			maTranCanh[j][1] = temp;

			temp = maTranCanh[i][0];
			maTranCanh[i][0] = maTranCanh[j][0];
			maTranCanh[j][0] = temp;

			i++; j--;
		}
		else {
			if (i < right) quickSort(i, right);
			if (left < j) quickSort(left, j);
			return;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	//freopen("input.txt", "r", stdin);
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		cin >> N;
		formatData();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> inputArr[i][j];
				if (i < j) {
					maTranCanh[indMaTranCanh][0] = i;
					maTranCanh[indMaTranCanh][1] = j;
					maTranCanh[indMaTranCanh++][2] = inputArr[i][j];
				}
			}
		}
		
		quickSort(0, indMaTranCanh - 1);

		for (int i = 0; i < indMaTranCanh; i++) {
			if (findSet(maTranCanh[i][0]) != findSet(maTranCanh[i][1])) {
				jointSet(maTranCanh[i][0], maTranCanh[i][1]);
				result += maTranCanh[i][2];
			}
		}

		cout << "Case #" << tc << endl;
		cout << result << endl;
	}
	return 0;
}