#include<bits/stdc++.h>
#define ll long long
const int maxN = 411;
const ll oo = 1000000000000000ll;
#define int long long
int vx[maxN];
int vy[maxN];
int lx[maxN];
int ly[maxN];
int slack[maxN];
int w[maxN][maxN];

int pre[maxN];
int left[maxN];
int right[maxN];

int N;

void match(int& u) {
  for(;u; std::swap(u, right[pre[u]]))
    left[u] = pre[u];
}

void bfs(int u) {
  static int q[maxN], front, rear;
  front = 0; vx[q[rear = 1] = u] = true;
    
  __builtin_prefetch(slack);
  while(true) {
    while(front < rear) {
      int u = q[++front];
      for(int v = 1;v <= N; ++v) {
        int tmp;
        if(vy[v] || (tmp = lx[u] + ly[v] - w[u][v]) > slack[v])
          continue;
        pre[v] = u;
        if(!tmp) {
          if(!left[v]) return match(v);
          vy[v] = vx[q[++rear] = left[v]] = true;
        } else slack[v] = tmp;
      }
    }

    int a = oo;
    for(int i = 1;i <= N; ++i)
      if(!vy[i] && a > slack[i]) a = slack[u = i];
    for(int i = 1;i <= N; ++i) {
      if(vx[i]) lx[i] -= a;
      if(vy[i]) ly[i] += a;
      else slack[i] -= a;
    }
    if(!left[u]) return match(u);
    vy[u] = vx[q[++rear] = left[u]] = true;
  }
}

void exec() {
  for(int i = 1;i <= N; ++i) {
    for(int j = 1;j <= N; ++j) {
      slack[j] = oo;
      vx[j] = vy[j] = false;
    }
    bfs(i);
  }
}
#undef int
int main()
{
    int ts;
    scanf("%d", &ts);
    for(int i = 1; i <= ts; i++)
    {
        scanf("%d", &N);
        memset(lx, 0, sizeof(lx)), 
        memset(ly, 0, sizeof(ly));
        memset(vx, 0, sizeof(vx)), 
        memset(vy, 0, sizeof(vy));
        memset(slack, 0, sizeof(slack)), 
        memset(w, 0, sizeof(w)),
        memset(pre, 0, sizeof(pre));
        memset(left, 0, sizeof(left));
        memset(right, 0, sizeof(right));
        
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++)
                scanf("%I64d", &w[i][j]), 
                w[i][j] = 1000000005 - w[i][j];
        exec();
        ll ans = 0;
        for(int i = 1; i <= N; i++)
            ans += lx[i] + ly[i];
        ans = 1000000005 * (ll)N - ans;
        printf("Case #%d: %I64d\n", i, ans);
    }
        
}