/*
    Jordan Werthman and Charley
    10/22/2011
    Permutations of tour times.
*/

#include <stdio.h>

//Prototype for function declaration
int perm(int used[], int index, int indicies[], int size, int times[8][8]);

int main() {
    //Open file to read in data
    FILE* ifp = fopen("tours.in","r");

    //Read in number of test cases for file
    int testCases;
    fscanf(ifp, "%d", &testCases);

    //Loop variables
    int i, j, k;

    //Loop through each test case
    for(i=0; i<testCases; i++) {
        //Read in number of lines in each test case
        int numLines;
        fscanf(ifp, "%d", &numLines);

        //Array to store all times
        int times[8][8];

        //Zero out array 'times'
        for(k=0; k<8; k++)
            for(j=0; j<8; j++)
                times[k][j]=0;

        //Read in all times from file into 2D array 'times'
        for(j=0; j<numLines; j++) {
            for(k=0; k<numLines; k++) {
                fscanf(ifp, "%d", &times[j][k]);
            }
        }

        //Declare blank variables for perm function
        int used[numLines];
        for(j=0; j<numLines; j++)
            used[j] = 0;
        int index = 0;
        int indices[numLines];
        for(j=0; j<numLines; j++)
            indices[j] = 0;
        int size = numLines;

        //Call permutation function which will return minimum value
        int result = perm(used, index, indices, size, times);

        //Print results
        printf("Case #%d: %d minutes\n",i+1, result);
    }

    //Exit code
    return 0;
}

/* Function to figure out all permutations and return the smallest cost
    Arguments: array containing used values, the current index, the array
        containing the permuted indicies, the desired size of the permutation,
        and the array containing all times
    Returns: smallest time cost
*/
int perm(int used[], int index, int indicies[], int size, int times[8][8]) {
    //Declare two loop variables and a variable to contain answer (set to large number to calculate minimum)
    int i, b, answer = 1000;

    //Base case: if desired size is reached quit recursion
    if(index==size) {
        //Calculate total time used by this path
        int total=0;

        //Loop through all indicies created by perm function
        for(i=0; i<size; i++) {
            //Allows for 'loop back' and keeps it from going out of bounds
            if(size-1==i)
                b = 0;
            else
                b = i+1;

            //Calculate total time by reading in each time at the permuted indicies
            total+=times[indicies[i]][indicies[b]];
        }

        //Return total time for this path
        return total;
    } else {
        //Permute
        for(i=0; i<size; i++) {
            //if this index has not been used already
            if(!used[i]) {
                //Set it to used
                used[i]=1;

                //Set the permuted array index to that value
                indicies[index]=i;

                //Call the function recursively and store return (total time from base case)
                int t = perm(used, index+1, indicies, size, times);

                //If the total is less then the current answer then set answer to total
                if(t<answer)
                    answer = t;

                //Set this index back to unsed for next attempt
                used[i]=0;
            }
        }
    }

    //Return answer
    return answer;
}