#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<stack>

#define P 20000

#define E 200000

using namespace std;

int i,j,k,n,T,ans,K,m,x,y,indexs,nn,mm;

int ru[P],head[P],head2[P],dfn[P],low[P],instack[P],belong[P];

bool b[E];

stack <int> tar;

struct node

{

	int from;

	int to;

	int next;

}map[E],map2[E];

void addedge(int num,int x,int y)

{

	map[num].from=x;

	map[num].to=y;

	map[num].next=head[x];

	head[x]=num;

}

void addedge2(int num,int x,int y)

{

	//printf("NewEdge %d %d\n",x,y); 

	ru[y]++;

	map2[num].from=x;

	map2[num].to=y;

	map2[num].next=head2[x];

	head2[x]=num;

}

void dfs(int p)

{

	for (int i=head2[p];i!=-1;i=map2[i].next)

	{

		if (!b[map2[i].to])

		{

			b[map2[i].to]=true;

			dfs(map2[i].to);

		}

	}

}

void tarjan(int k)

{

    int p;

    tar.push(k);

    instack[k]=1;

    dfn[k]=low[k]=++indexs;

    for(int j=head[k];j!=-1;j=map[j].next)

    {

        p=map[j].to;

        if (instack[p])

		{

			low[k]=min(low[k],dfn[p]);

		}

        else

		if(dfn[p]==-1)

        {

            tarjan(p);

            low[k]=min(low[k],low[p]);

        }

    }

    if(low[k]==dfn[k])

    {

        nn++;

        do

        {

            j=tar.top();

            tar.pop();

            instack[j]=0;

            belong[j]=nn;

        }while(j!=k);

    }

}

void build_new_map()

{

    for(int i=1;i<=m;i++)

    {

        if(belong[map[i].from]==belong[map[i].to])

			continue;

        addedge2(++mm,belong[map[i].from],belong[map[i].to]);

    }

}

void build_map()

{

	scanf("%d%d",&n,&m);

	for (i=1;i<=m;i++)

	{

		scanf("%d%d",&x,&y);

		addedge(i,x,y);

	}

	memset(dfn,-1,sizeof(dfn));

	memset(low,-1,sizeof(low));

	memset(instack,0,sizeof(instack));

	indexs=0;nn=0;

	for (i=1;i<=n;i++) belong[i]=i;

	for (i=1;i<=n;i++)

	{

		if (dfn[i]==-1)

			tarjan(i);

	}

	build_new_map();

}

int main()

{

	scanf("%d",&T);

	while (++K<=T)

	{

		memset(map,-1,sizeof(map));

		memset(head,-1,sizeof(head));

		memset(map2,-1,sizeof(map2));

		memset(head2,-1,sizeof(head2));

		memset(b,0,sizeof(b));

		memset(ru,0,sizeof(ru));

		ans=0;mm=0;nn=0;

		build_map();

		for (i=1;i<=nn;i++)

		{

			if (!ru[i])

			{

				ans++;

				b[i]=true;

				dfs(i);

			}

		}

		for (i=1;i<=nn;i++)

		{

			if (!b[i])

			{

				ans++;

			 	b[i]=true;

				dfs(i);

			}

		}

		printf("Case %d: %d\n",K,ans);

	}

}