#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fr(n,k) for(int i=n;i<k;i++)

int vis[20005];
vector<int>vc[20005];
void bfs(int x){
    queue<int>q;
    q.push(x);
    vis[x]=1;
    while(!q.empty()){
        int u=q.front();
        int v;
        q.pop();
        fr(0,vc[u].size()){
            if(vis[u]==1){
                v=vc[u][i];
                vis[v]=2;
                q.push(v);
            }
            else if(vis[u]==2){
                int v=vc[u][i];
                vis[v]=1;
                q.push(v);
            }
        }
        vc[v].clear();
    }
}

int main()
{
    int t;
    cin>>t;
    int i=1;
    while(t--){
        int n;
        int mx;
        set<int>st;
        cin>>n;
        fr(0,n){
            int x,y;
            cin>>x>>y;
            vc[x].pb(y);vc[y].pb(x);
            st.insert(x);
            st.insert(y);
        }
        for(auto it=st.begin();it!=st.end();it++){
            if(vis[*it])continue;
            bfs(*it);

        }
        int b=0,w=0;
        for(auto it=st.begin();it!=st.end();it++){
            if(vis[*it]==1)w++;
            else if(vis[*it])b++;
        }
        if(w>b)mx=w;
        else mx=b;

        cout<<"Case "<<i<<": "<<mx<<endl;
        i++;
        memset(vis,0,sizeof(vis));
    }
    return 0;
}