#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define sz(x) (int)(x).size()
#define li long long
#define ld long double
#define x first
#define y second
#define pt pair<int, int>
#define pll pair<li, li>
#define forn(i, t) for(int i = 0; i < (t); i++)
#define fore(i, f, t) for(int i = (f); i < (t); i++)
#define forr(i, f, t) for(int i = (f) - 1; i >= (t); i--)
#define all(x) (x).begin(), (x).end()
#define ins insert

using namespace std;


const int INF = 1e9;
const int MOD = 1e9 + 7;
const li INF64 = 1e18;
const ld EPS = 1e-7;

mt19937 myrand(time(NULL));

const int N = 1000 + 13;

int n, c, m;
vector<int> g[N];


bool read(){
    if(scanf("%d%d%d", &n, &c, &m) != 3)
        return 0;
    forn(i, c)
        g[i] = vector<int>();
    int f, t;
    forn(i, m){
        scanf("%d%d", &f, &t);
        --f, --t;
        g[t].pb(f);
    }
    return 1;
}


struct ed{
    int x, y, w, d, f;
    ed(int x, int y, int w, int d, int f) : x(x), y(y), w(w), d(d), f(f) {};
    ed(){};
};


bool operator <(const ed &a, const ed &b){
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}


bool operator ==(const ed &a, const ed &b){
    return (a.x == b.x) && (a.y == b.y);
}


vector<ed> edges;
int p[2 * N];


int blm(int v){
    int st = sz(g[0]) + sz(g[1]);
    int en = st + 1;

    vector<int> d(en + 1, INF);
    d[v] = 0;
    while (1){
        bool fl = 0;
        for (auto it = edges.begin(); it != edges.end(); it++){
            auto e = *it;
            if (e.f < e.d && d[e.x] < INF && d[e.y] > d[e.x] + e.w){
                d[e.y] = d[e.x] + e.w;
                p[e.y] = e.x;
                fl = 1;
            }
        }
        if (!fl)
            break;
    }

    if (d[en] == INF)
        return 0;

    int cur = en, dt = INF;
    while (cur != v){
        auto it = lower_bound(all(edges), ed(p[cur], cur, 0, 0, 0));
        dt = min(dt, it->d - it->f);

        cur = p[cur];
    }

    cur = en;
    while (cur != v){
        int tmp = lower_bound(all(edges), ed(p[cur], cur, 0, 0, 0)) - edges.begin();
        int rtmp = lower_bound(all(edges), ed(cur, p[cur], 0, 0, 0)) - edges.begin();

        edges[tmp].f += dt;
        edges[rtmp].f -= dt;

        cur = p[cur];
    }

    return dt;
}


void solve(){
    int ans = 0;
    int cnt1 = 0, cnt2 = 0;

    sort(all(g[0]));
    sort(all(g[1]));

    if (sz(g[0]) > sz(g[1]))
        swap(g[0], g[1]);

    int cnt11 = 0, cnt21 = 0, cnt12 = 0, cnt22 = 0;

    for (auto it : g[0])
        if (it)
            cnt12++;
        else
            cnt11++;

    for (auto it : g[1])
        if (it)
            cnt22++;
        else
            cnt21++;

    int k = min(cnt21, cnt12);
    cnt12 -= k;
    cnt21 -= k;
    ans += k;
    k = min(cnt22, cnt11);
    cnt11 -= k;
    cnt22 -= k;
    ans += k;

    ans += max(cnt12, cnt22);

    ans += cnt11 + cnt21;

    reverse(all(g[0]));
    forn(i, cnt11)
        g[0].pop_back();
    reverse(all(g[0]));

    reverse(all(g[1]));
    forn(i, cnt21)
        g[1].pop_back();
    reverse(all(g[1]));

    edges = vector<ed>();

    cnt2 = sz(g[0]) + sz(g[1]);

    forn(i, sz(g[0]))
        forn(j, sz(g[1]))
            if (g[0][i] != 0 || g[1][j] != 0){
                if (g[0][i] == g[1][j]){
                    edges.pb(ed(j + sz(g[0]), i, -1, 0, 0));
                    edges.pb(ed(i, j + sz(g[0]), 1, 1, 0));
                }
                else{
                    edges.pb(ed(j + sz(g[0]), i, 0, 0, 0));
                    edges.pb(ed(i, j + sz(g[0]), 0, 1, 0));
                }
            }

    forn(i, sz(g[0])){
        //printf("///%d %d\n", cnt2, i);
        edges.pb(ed(i, cnt2, -10000, 0, 0));
        edges.pb(ed(cnt2, i, 10000, 1, 0));
    }

    ++cnt2;

    forn(i, sz(g[1])){
        //printf("////%d %d\n", cnt1 + i, cnt2);
        edges.pb(ed(cnt2, i + sz(g[0]), -10000, 0, 0));
        edges.pb(ed(i + sz(g[0]), cnt2, 10000, 1, 0));
    }

    sort(all(edges));

    --cnt2;

    int res = blm(cnt2);
    while (res)
        res = blm(cnt2);

    //for (auto it : edges)
    //  if (it.d)
    //      printf("%d %d %d\n", it.x, it.y, it.f);

    int sum = 0;
    forn(i, sz(g[0]))
        fore(j, sz(g[0]), sz(g[0]) + sz(g[1])){
            auto it = lower_bound(all(edges), ed(i, j, 0, 0, 0));
            if (it != edges.end() && it->f != 0){
                sum += it->w;
                //printf("%d %d\n", g[0][i], g[1][j]);
            }
        }

    printf("%d %d\n", ans, sum);
}


int main(){
    #ifdef _DEBUG
        freopen("input.txt", "r", stdin);
    #endif
    int n;
    scanf("%d\n", &n);
    forn(i, n){
        read();
        printf("Case #%d: ", i + 1);
        solve();
    }
    return 0;
}