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

vector<vector<int> >g(20005);
bool vis[20005];

int xx,yy,a,b,n,t;

void dfs(int source, bool p)
{
    if(vis[source]==true)
    return;
    vis[source]=true;
    if(p)
    xx++;
    else
    yy++;
    int sz=g[source].size();
    for(int i=0;i<sz;i++)
    dfs(g[source][i],!p);
    return;
}

int main()
{
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        memset(vis,false,sizeof vis);
        for(int j=0;j<=20004;j++)
        g[j].clear();

        cin>>n;
        for(int j=1;j<=n;j++)
        {
            scanf("%d%d",&a,&b);
            g[a].push_back(b);
            g[b].push_back(a);
        }
        int ans=0;
        for(int j=1;j<=20003;j++)
        if(vis[j]==false && g[j].size()>0)
        {
            xx=yy=0;
            dfs(j,true);
            ans+=max(xx,yy);
        }
        cout<<"Case "<<i<<": "<<ans<<endl;
    }
    return 0;
}