#include <bits/stdc++.h>
using namespace std;

int rooms[55][55];
int parent[55],n;
#define edges pair <int,int>
vector < pair <int, edges> > abid;
bool check;

int get_parent(int x)
{
	if(x!=parent[x])
		parent[x]=get_parent(parent[x]);

	return parent[x];
}

int kruskal()
{
	int total=0;
	int pu,pv,i;
	sort(abid.begin(),abid.end());

	for(i=0;i<abid.size();i++)
	{
		pu=get_parent(abid[i].second.first);
		pv=get_parent(abid[i].second.second);

		if(pu!=pv)
		{
			total+=abid[i].first;
			parent[pu]=parent[pv];
		}

	}
	return total;
}

int main()
{
	int T,cs=1;
	scanf("%d",&T);
	while(T--)
	{
		int min_wire=0,donation=0,total_wire=0,i,j;
		scanf("%d",&n);
		total_wire=0;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				scanf("%d",&rooms[i][j]);
				if(j!=i && rooms[i][j]!=0)
				{
					abid.push_back( pair<int,edges> (rooms[i][j],edges(i,j)));
				}
				total_wire+=rooms[i][j];
			}

		for(i=1;i<=n;i++)
			parent[i]=i;

		min_wire=kruskal();
		donation=total_wire-min_wire;
		check=1;
		for(i=1;i<n;i++)
			if(parent[i]!=parent[i+1])
			{
				printf("Case %d: -1\n",cs++);
				check=0;
				break;
			}

		if(check)
			printf("Case %d: %d\n",cs++,donation);
		abid.clear();
	}

	return 0;

}