#include <bits/stdc++.h>
using namespace std;
typedef long long Long;
#define int Long
const int maxN = 400;
const Long inf = 1e18;
int n, nL, nR, cost[maxN + 10][maxN + 10], lk[maxN + 10], od[maxN + 10], t;
Long wL[maxN + 10], wR[maxN + 10], slk[maxN + 10], ans; 
bool visL[maxN + 10], visR[maxN + 10];

bool Dfs(int p) {
    visL[p] = 1;
    for (int i = 1; i <= n; ++i)
        if (!visR[i]){
            Long d = wL[p] + wR[i] - cost[p][i];
            if (!d) {
                visR[i] = 1;
                if (!lk[i] || Dfs(lk[i])) {
                    lk[i] = p; return 1;
                }
            } else slk[i] = min(slk[i], d);
        }
    return 0;
}

void KM() {
    n = max(nL, nR);
    ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            wL[i] = max(wL[i], (Long)cost[i][j]);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            slk[j] = inf; visL[j] = visR[j] = 0;
        }
        if (!Dfs(i)) {
            while (1) {
                Long d = inf; int pos;
                for (int j = 1; j <= n; ++j) 
                    if (!visR[j]) d = min(d, slk[j]);
                for (int j = 1; j <= n; ++j) {
                    if (visL[j]) wL[j] -= d;
                    if (visR[j]) wR[j] += d;
                    else {
                        slk[j] -= d;
                        if (!slk[j]) pos = j;
                    }
                }
                if (!lk[pos]) break;
                int p = lk[pos]; visL[p] = visR[pos] = 1;
                for (int j = 1; j <= n; ++j)
                    slk[j] = min(slk[j], wL[p] + wR[j] - cost[p][j]);
            }
            for (int j = 1; j <= n; ++j) visL[j] = visR[j]  = 0;
            Dfs(i);
        }
    }
    for (int i = 1; i <= n; ++i)
        ans += wL[i] + wR[i];
    printf("%lld\n", -ans);
}

main() {
    scanf("%lld", &t);
    for (int cas = 1; cas <= t; ++cas) {
        memset(cost, 0, sizeof cost);
        memset(lk, 0, sizeof lk);
        memset(od, 0, sizeof od);
        memset(wL, 0, sizeof wL);
        memset(wR, 0, sizeof wR);
        memset(slk, 0, sizeof slk);
        memset(visL, 0, sizeof visR);
        scanf("%lld", &n);
        nL = nR = n;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) {
                scanf("%lld", &cost[i][j]);
                cost[i][j] = -cost[i][j];
            }
        printf("Case #%lld: ", cas);
        KM();
    }
}