// Stephen Fulwider
//	UCF Tours - BHCSI 2010 Programming Contest

import java.io.File;
import java.util.Scanner;


public class tours
{

	public static void main(String[] args) throws Exception
	{
		new tours();
	}
	
	int N; // number of nodes
	int[][] G=new int[8][8]; // adj matrix
	
	tours() throws Exception
	{
		Scanner in=new Scanner(new File("tours.in"));
		for (int T=in.nextInt(),TC=1; T-->0; ++TC)
		{
			// read in graph
			N=in.nextInt();
			for (int i=0; i<N; ++i)
				for (int j=0; j<N; ++j)
					G[i][j]=in.nextInt();
			
			// try all permutations and return min tour
			//	note that we could fix the first spot, but i'll just try all N! anyway
			int min=permute(0,new int[N],new boolean[N]);
			System.out.printf("Case #%d: %d minutes%n",TC,min);
		}
	}
	
	int permute(int at, int[] perm, boolean[] used)
	{
		// done building a permutation
		if (at==N)
		{
			// sum the tour
			int res=0;
			for (int i=0; i<N; ++i)
				res+=G[perm[i]][perm[(i+1)%N]]; // do %N here to connect the last spot back to first
			return res;
		}
		
		// try all unused elements and keep the min value
		int min=Integer.MAX_VALUE;
		for (int i=0; i<N; ++i)
			if (!used[i])
			{
				used[i]=true;
				perm[at]=i;
				min=Math.min(min,permute(at+1,perm,used));
				used[i]=false;
			}
		return min;
	}

}