#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 0x7f7f7f7f

using namespace std;

typedef long long ll;

int c[205][205];
int dx[205],dy[205];
int link[205],pre[205];
int sl[205];
bool vis[205];

void bfs(int x,int n) {
  memset(vis,0,sizeof(vis));
  memset(pre,0,sizeof(pre));
  memset(sl,0x7f,sizeof(sl));
  int nx=0,ny=0;
  link[ny]=x;
  do {
      nx=link[ny];vis[ny]=1;
      int d=inf,t=0;
      for(int i=1;i<=n;i++)
        if (!vis[i]) {
              int cost=dx[nx]+dy[i]-c[nx][i];
              if (cost<sl[i]) {
                      sl[i]=cost;pre[i]=ny;
              }
          if (sl[i]<d) {
                  d=sl[i];t=i;
          }
        }
    for(int i=0;i<=n;i++)
      if (vis[i]) {
          dx[link[i]]-=d;dy[i]+=d;
      }
      else sl[i]-=d;
    ny=t;
  } while (link[ny]);
  for(;ny;ny=pre[ny]) link[ny]=link[pre[ny]];
}

void km(int n) {
  memset(link,0,sizeof(link));
  memset(dy,0,sizeof(dy));
  for(int i=1;i<=n;i++) {
      dx[i]=-inf;
      for(int j=1;j<=n;j++) dx[i]=max(dx[i],c[i][j]);
  }
  for(int i=1;i<=n;i++) bfs(i,n);
}

int main() {
  int cases;
  scanf("%d",&cases);
  for(int t=1;t<=cases;t++) {
      int n;
      scanf("%d",&n);
      for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) {
              int x;
              scanf("%d",&x);
              c[i][j]=-x;
        }
    km(n);
    ll ans=0;
    for(int i=1;i<=n;i++) ans+=c[link[i]][i];
    printf("Case #%d: %I64d\n",t,-ans);
  }
  return 0;
}