#include<bits/stdc++.h>
#define cls(a) memset(a,0,sizeof a)
using namespace std;
typedef unsigned u32;
typedef long long i64;
const u32 offset=1<<31;
const u32 M=405;
const u32 INF=0x7F7F7F7F;
inline void chkmax(u32&a,const u32&b){
    a=a<b?b:a;
}
inline void chkmin(u32&a,const u32&b){
    a=a>b?b:a;
}
struct ano{
    operator u32(){
        signed x=0,y=0,c=getchar();
        while(c<48)
            y=c==45,c=getchar();
        while(c>47)
            x=x*10+c-48,c=getchar();
        return y?-x:x;
    }
}buf;
u32 nl,nr,n,m,D[M][M];
u32 A[M],L[M];
u32 To[M],Slack[M];
bool Vis[M];
u32 Q[M],Pre[M];
void Updata(){
    u32 d=INF;
    for(u32 i=1;i<n+1;++i)
        if(!Vis[i])
            chkmin(d,Slack[i]);
    for(u32 i=1;i<n+1;++i)
        if(Vis[i])
            L[i]+=d;
    else Slack[i]-=d;
    for(u32 i=n+1;i<n+n+1;++i)
        if(Vis[i])
            L[i]-=d;
}
u32 BFS(u32 x){
    u32 l,r;
    l=r=0;
    Vis[Q[r++]=x]=1;
    while(1){
        while(l<r){
            u32 A=Q[l++];
            for(u32 B=1;B<n+1;++B)
                if(!Vis[B]){
                    u32 d=L[A]+L[B]-D[B][A];
                    if(d>Slack[B])
                        continue;
                    Pre[B]=A;
                    if(!d){
                        Vis[B]=1;
                        if(!To[B])
                            return B;
                        else Vis[Q[r++]=To[B]]=1;
                    }
                    else Slack[B]=d;
                }
        }
        Updata();
        for(u32 B=1;B<n+1;++B)
            if(!Vis[B]&&!Slack[B]){
                Vis[B]=1;
                if(!To[B])
                    return B;
                else Vis[Q[r++]=To[B]]=1;
            }
    }
    return-1;
}
void Solve(){
    cls(D);
    cls(A);
    cls(L);
    cls(To);
    cls(Slack);
    cls(Vis);
    cls(Q);
    cls(Pre);
    nl=nr=n=buf;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j){
            u32 w=offset-buf;
            chkmax(D[i][n+j],w);
            chkmax(A[i],w);
        }
    for(u32 i=1;i<n+1;++i)
        L[i]=A[i];
    for(u32 i=n+1;i<n+n+1;++i){
        memset(Slack,0x7F,sizeof(u32)*(n+4));
        memset(Vis,0,sizeof(Vis));
        u32 x=BFS(i);
        while(x)
            swap(x,To[To[x]=Pre[x]]);
    }
    i64 Ans=0;
    for(u32 i=1;i<nl+1;++i)
        Ans+=D[i][To[i]];
    printf("%I64d\n",(i64)n*offset-Ans);
}
int main(){
    int t=buf;
    for(int i=1;i<=t;++i){
        printf("Case #%d: ",i);
        Solve();
    }
}