#include <bits/stdc++.h>
using namespace std;
vector<int>v[20009];
queue<int>q;
map<int,bool>vis,color;
int main() {
	// your code goes here
	int t;
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		int n,x;
		cin>>n;
		while(n--)
		{
			int u,m;
			cin>>u>>m;
			v[u].push_back(m);
			v[m].push_back(u);
			x=u;
		}
		int black=0,red=0;
        color[x]=0;
        red++;
        q.push(x);
        while(!q.empty())
        {
        	int s=q.front();
        	q.pop();
        	for(int i=0;i<v[s].size();i++)
        	{
        		if(!vis[v[s][i]])
        		{
        			if(color[s]==0)
        			{
        				color[v[s][i]]=1;
        				black++;
        			}
        			else if(color[s]==1)
        			{
        				color[v[s][i]]=0;
        				red++;
        			 }
        			 q.push(v[s][i]);
        			 vis[v[s][i]]=1;
        		}
        	}
        }
        cout<<"Case "<<i<<":"<<" "<<max(red,black)<<endl;
        for(int i=0;i<20009;i++)
         v[i].clear();
        vis.clear();
        color.clear();
     }
	return 0;
}