#include <bits/stdc++.h>

using namespace std;

const int N = 128;
const int INF = (1e9) + 7;

struct edge {
    int to,reversed,flow,capacity,cost;
    edge(){}
    edge(int a, int b, int c, int d) {
        to=a;
        reversed=b;
        flow=0;
        capacity=c;
        cost=d;
    }
};

struct el {
    int vertex,cost;
    el(){}
    el(int a, int b) {
        vertex=a;
        cost=b;
    }
    bool operator <(const el &a) const {
        return cost>a.cost;
    }
};

int tests,current_case;
int n,a[N][N];
int nodes,s,t;
vector < edge > v[N];
priority_queue < el > q;
int dist[N],from[N];
int current_flow[N];
int link[N];
int pot[N];

void initialize_data() {
    int i;
    for(i=0;i<N;i++) v[i].clear();
}

void message(int current_case) {
    fprintf(stderr, "Case %d solved!\n", current_case);
}

void add_edge(int a, int b, int c, int d) {
    edge x=edge(b,v[b].size(),c,d);
    edge y=edge(a,v[a].size(),0,-d);
    v[a].push_back(x);
    v[b].push_back(y);
}

void bellman_ford() {
    int i,j,z;
    for(i=1;i<=nodes;i++) pot[i]=INF;
    pot[s]=0;
    for(i=1;i<nodes;i++) {
        for(j=1;j<=nodes;j++) {
            for(z=0;z<(int)(v[j].size());z++) {
                dist[v[j][z].to]=min(dist[v[j][z].to],dist[j]+v[j][z].cost);
            }
        }
    }
}

pair < int, int > mincost_maxflow(int flow) {
    int i,current_distance,to,w;
    el curr;
    int max_flow=0,min_cost=0,transmitted,where,prev;

    bellman_ford();
    while(max_flow<flow) {
        for(i=1;i<=nodes;i++) dist[i]=INF,current_flow[i]=0,from[i]=-1;
        dist[s]=0;
        current_flow[s]=INF;
        q.push(el(s,0));
        while(!q.empty()) {
            curr=q.top();
            q.pop();
            for(i=0;i<(int)(v[curr.vertex].size());i++) if(v[curr.vertex][i].flow<v[curr.vertex][i].capacity) {
                to=v[curr.vertex][i].to;
                w=v[curr.vertex][i].cost;
                current_distance=curr.cost+w+pot[curr.vertex]-pot[to];
                if(current_distance<dist[to]) {
                    dist[to]=current_distance;
                    current_flow[to]=min(current_flow[curr.vertex],v[curr.vertex][i].capacity-v[curr.vertex][i].flow);
                    link[to]=i;
                    from[to]=curr.vertex;
                    q.push(el(to,current_distance));
                }
            }
        }
        if(current_flow[t]==0) break;
        transmitted=min(current_flow[t],flow-max_flow);
        max_flow+=transmitted;
        where=t;
        while((prev=from[where])!=(-1)) {
            v[prev][link[where]].flow+=transmitted;
            v[where][v[prev][link[where]].reversed].flow-=transmitted;
            min_cost+=transmitted*v[prev][link[where]].cost;
            where=prev;
        }
    }
    return make_pair(max_flow,min_cost);
}

int main() {
    pair < int, int > ans;
    int i,j;

    scanf("%d", &tests);
    for(current_case=1;current_case<=tests;current_case++) {
        initialize_data();
        scanf("%d", &n);
        for(i=1;i<=n;i++) {
            for(j=1;j<=n;j++) {
                scanf("%d", &a[i][j]);
            }
        }
        nodes=n+n+2;
        s=nodes-1;
        t=nodes;
        for(i=1;i<=n;i++) add_edge(s,i,1,0);
        for(i=1;i<=n;i++) {
            for(j=1;j<=n;j++) {
                add_edge(i,n+j,1,-a[i][j]);
            }
        }
        for(i=1;i<=n;i++) add_edge(n+i,t,1,0);
        ans=mincost_maxflow(n);
        printf("Case %d: %d\n", current_case, -ans.second);
        message(current_case);
    }

    return 0;
}