//Relive your past life.
//Face your demons.
//The past is never dead,it is not even past.
//The memories are not only the key to the past but...also to the future.
//coded in Rusty Lake
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define ll   long long
#define pb   push_back
#define mp   make_pair
#define orz  1000000007
#define REP(i,a,b) for(int i=(a);i<(b);++i)
#define M 404
#define INF 0x3f3f3f3f
using namespace std;
inline void chkmax(int &a,const int &b){if(a<b)a=b;}
inline void chkmin(int &a,const int &b){if(a>b)a=b;}
int nl,nr,n,D[M][M];
int A[M],L[M];
int To[M],Slack[M];
bool Vis[M];
int Q[M],Pre[M];
void Updata(){
    int d=INF;
    REP(i,1,n+1)if(!Vis[i])chkmin(d,Slack[i]);
    REP(i,1,n+1)if(Vis[i])L[i]+=d;
    else Slack[i]-=d;
    REP(i,n+1,n+n+1)if(Vis[i])L[i]-=d;
}
int BFS(int x){
    int l,r;
    l=r=0;
    Vis[Q[r++]=x]=1;
    while(1){
        while(l<r){
            int A=Q[l++];
            REP(B,1,n+1)if(!Vis[B]){
                int 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();
        REP(B,1,n+1)if(!Vis[B] && !Slack[B]){
            Vis[B]=1;
            if(!To[B])return B;
            else Vis[Q[r++]=To[B]]=1;
        }
    }
    return -1;
}
ll Solve(){
    REP(i,n+1,n+n+1){
        memset(Slack,63,sizeof(int)*(n+4));
        memset(Vis,0,sizeof(Vis));
        int x=BFS(i);
        while(x)swap(x,To[To[x]=Pre[x]]);
    }
    long long Ans=0;
    REP(i,1,nl+1)Ans+=D[i][To[i]];
    return -Ans;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int _=1;_<=T;++_){
        memset(D,0,sizeof(D));
        memset(A,0,sizeof(A));
        memset(L,0,sizeof(L));
        memset(To,0,sizeof(To));
        memset(Q,0,sizeof(Q));
        memset(Pre,0,sizeof(Pre));
        printf("Case #%d: ",_);
        scanf("%d",&n);
        nl=nr=n;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                int o;
                scanf("%d",&o);
                o=orz-o;
                chkmax(D[i][j+n],o);
                chkmax(A[i],o);
            }
        }
        REP(i,1,n+1)L[i]=A[i];
        srand(time(0));
        printf("%I64d\n",n*1ll*orz+Solve());
    }
   // system("pause");
    return 0;
}