#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <cstring>
#include <cstdlib>
#include <map>
#include <ctime>
#include <queue>
#include <bitset>

using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define forit(s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)
#define forn(i, l, r) for(int i = l; i < r; i ++)
#define pii pair <int, int>
#define vi vector <int>
#define N 1005
#define y1 stupid_cmath
#define sz(a) (int)a.size()
#define ll long long
#define all(a) a.begin(), a.end()

const int inf = (int)1e9;
const int mod = (int)1e9 + 7;
const double pi = acos(-1.0);
const double eps = 1e-9;

int n, m, col[N];
vi g[N], gr[N], order;
pii e[10 * N];
int used[N], mt[N], c, sz, ver = 1;
int was[N][N];
vector <bitset <N> > b;

void clear() {
	b.clear();
	for(int i = 0; i < N; i++) {
		g[i].clear();
		gr[i].clear();
	}
	order.clear();
	memset(col, 0, sizeof col);
	sz = 0;
	c = 1;
	memset(mt, -1, sizeof mt);
	memset(used, 0, sizeof used);
}

void dfs1(int v) {
	used[v] = 1;
	forit(gr[v]) {
		if(!used[*it]) dfs1(*it);
	}
	order.pb(v);
}

void dfs2(int v) {
	used[v] = 1;
	col[v] = sz;
	forit(g[v]) {
		if(!used[*it]) dfs2(*it);
	}
}

void dfs3(int v) {
	used[v] = 1;
	forit(gr[v]) {
		int to = *it;
		if(used[to]) continue;
		dfs3(to);
	}
	order.pb(v);
}

void read() {
	scanf("%d%d", &n, &m);
	for(int i = 0, x, y; i < m; i++) {
		scanf("%d%d", &x, &y);
		x--; y--;
		e[i] = (mp(x, y));
		g[x].pb(y); gr[y].pb(x);
	}
	for(int i = 0; i < n; i++)
		if(!used[i]) dfs1(i);
	reverse(all(order));
	memset(used, 0, sizeof used);
	for(int i = 0; i < n; i++) {
		int v = order[i];
		if(!used[v]) {
			dfs2(v);
			sz++;
		}
	}

	for(int i = 0; i < N; i++) {gr[i].clear(); g[i].clear();}

	for(int i = 0; i < m; i++) {
		if(col[e[i].f] != col[e[i].s]) {
			int x = col[e[i].f], y = col[e[i].s];
			if(was[x][y] == ver) continue;
			was[x][y] = ver;
			gr[x].pb(y);
		}
	}




	order.clear();
	memset(used, 0, sizeof used);
	for(int i = 0; i < sz; i++) {
		if(!used[i]) dfs3(i);
	}
	b.assign(sz, bitset <N>(0));
	for(int i = 0; i < sz; i++) {
		int v = order[i];
		b[v][v] = 1;
		forit(gr[v]) {
			b[v] |= b[*it];
		}
	}
	for(int i = 0; i < sz; i++) {
		for(int j = 0; j < sz; j++) if(b[i][j] == 1 && i != j) g[i].pb(j);
	}
}

bool dfs(int v) {
	if(used[v] == c) return false;
	used[v] = c;
	forit(g[v]) {
		int i = *it;
		if(mt[i] == -1) {
			mt[i] = v;
			return true;
		}
	}
forit(g[v]) {
		int i = *it;
		if((mt[i] == -1 || dfs(mt[i]))) {
			mt[i] = v;
			return true;
		}
	}
	return false;
}

void solve(int num) {
	printf("Case %d: ", num);

	clear();
	read();

	int ans = 0;
	memset(used, 0, sizeof used);
	for(int i = 0; i < sz; i++) {
		ans += dfs(i);
		c++;
	}

	printf("%d\n", sz - ans);
	ver++;
}

int main () {

	#ifdef LOCAL
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    #endif

    int T;
    scanf("%d", &T);
    for(int i = 1; i <= T; i++) solve(i);

    return 0;
}