#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 100005
using namespace std;

bool viz[NMAX];
int timp[NMAX];
vector<int> v[NMAX];
int nr, t;


void DFS(int x) {
  viz[x] = 1;
  for(int i = 0; i < v[x].size(); ++i) {
    if(!viz[v[x][i]]) {
      DFS(v[x][i]);
    }
  }
  timp[++t] = x;
}


int main()
{
    int T, N, M, ans, x, y;
    cin >> T;
    for(int i = 1; i <= T; ++i) {
        cin >> N >> M;
        ans = 0;
        t = 0;
        for(int j = 1; j <= M; ++j) {
            cin >> x >> y;
            v[x].push_back(y);
        }
        for(int j = 1; j <= N; ++j) {
            if(!viz[j]) {
                DFS(j);
            }
        }
        for(int j = t; j >= 1; --j) {
            if(!viz[timp[j]]) {
                ++ans;
                DFS(timp[j]);
            }
        }
        for(int j = 1; j <= N; ++i) {
            viz[j] = 0;
            timp[j] = 0;
            v[j].clear();
        }
        cout << "Case " << i << ": " << ans << '\n';
    }
    return 0;
}