#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 10, MAXM = 1000000 + 10, inf = 1e9;

namespace NetFlow {
    struct Edge {
        int v, cap, nxt;
        Edge() {}
        Edge(int v, int c, int n) : v(v), cap(c), nxt(n) {}
    } E[MAXM];
    int G[MAXN], Q[MAXN], level[MAXN], cur[MAXN], pre[MAXN];
    int S, T, N, sz, sgn, maxflow;
    void init(int _n, int _s, int _t) {
        N = _n; S = _s; T = _t; sz = 0;;
        memset(G, -1, sizeof(G[0]) * N);
    }
    void addedge(int u, int v, int cap) {
        E[sz] = Edge(v, cap, G[u]); G[u] = sz ++;
        E[sz] = Edge(u, 0, G[v]); G[v] = sz ++;
    }
    bool bfs() {
        memset(level, -1, sizeof(level[0]) * N);
        level[T] = 0; Q[0] = T; sgn = T;
        for (int h = 0, t = 1; h < t && level[S] == -1; ++ h) {
            int u = Q[h], v;
            for (int now = G[u]; ~now; now = E[now].nxt) {
                if (E[now ^ 1].cap > 0 && level[v = E[now].v] == -1) {
                    level[v] = level[u] + 1; Q[t ++] = v;
                }
            }
        }
        return level[S] != -1;
    }
    inline void push() {
        int aug = inf;
        for (int u = T, now; u != S; u = E[now ^ 1].v) {
            aug = min(aug, E[now = pre[u]].cap);
        }
        for (int u = T, now; u != S; u = E[now ^ 1].v) {
            now = pre[u]; E[now].cap -= aug; E[now ^ 1].cap += aug;
            if (!E[now].cap) sgn = E[now ^ 1].v;
        }
        maxflow += aug;
    }
    void dfs(int u) {
        if (u == T) {push(); return;}
        for (int &now = cur[u]; ~now; now = E[now].nxt) { 
            int v = E[now].v;
            if (E[now].cap > 0 && level[u] == level[v] + 1) {
                pre[v] = now; dfs(v);
                if (level[sgn] > level[u]) return;
                sgn = T;
            }
        }
    }
    int flow() {
        maxflow = 0;
        while (bfs()) {
            memcpy(cur, G, sizeof(G[0]) * N);
            dfs(S);
        }
        return maxflow;
    }
}
int N, M, deg[MAXN];

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++ cas) {
        scanf("%d%d", &N, &M);
        NetFlow::init(N + 2, 0, N + 1);
        for (int i = 0; i <= N; ++ i) deg[i] = 0;
        while (M --) {
            char st[10]; int a, b, c;
            scanf("%s%d%d%d", st, &a, &b, &c);
            if (st[0] == 'F') {
                deg[a] -= 2; deg[b] ++; deg[c] ++;
                NetFlow::addedge(a, b, inf);
                NetFlow::addedge(a, c, inf);
            }
            else {
                deg[c] += 2; deg[a] --; deg[b] --;
                NetFlow::addedge(a, c, inf);
                NetFlow::addedge(b, c, inf);
            }
        }
        int sum = 0;
        for (int i = 1; i <= N; ++ i) {
            if (deg[i] > 0) {
                sum += deg[i];
                NetFlow::addedge(NetFlow::S, i, deg[i]);
            } else if (deg[i] < 0) {
                NetFlow::addedge(i, NetFlow::T, -deg[i]);
            }
        }
        printf("Case #%d: %d\n", cas, sum - NetFlow::flow());
    }
    return 0;
}