#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;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnZlY3RvcjxpbnQ+dlsyMDAwOV07CnF1ZXVlPGludD5xOwptYXA8aW50LGJvb2w+dmlzLGNvbG9yOwppbnQgbWFpbigpIHsKCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCWludCB0OwoJY2luPj50OwoJZm9yKGludCBpPTE7aTw9dDtpKyspCgl7CgkJaW50IG4seDsKCQljaW4+Pm47CgkJd2hpbGUobi0tKQoJCXsKCQkJaW50IHUsbTsKCQkJY2luPj51Pj5tOwoJCQl2W3VdLnB1c2hfYmFjayhtKTsKCQkJdlttXS5wdXNoX2JhY2sodSk7CgkJCXg9dTsKCQl9CgkJaW50IGJsYWNrPTAscmVkPTA7CiAgICAgICAgY29sb3JbeF09MDsKICAgICAgICByZWQrKzsKICAgICAgICBxLnB1c2goeCk7CiAgICAgICAgd2hpbGUoIXEuZW1wdHkoKSkKICAgICAgICB7CiAgICAgICAgCWludCBzPXEuZnJvbnQoKTsKICAgICAgICAJcS5wb3AoKTsKICAgICAgICAJZm9yKGludCBpPTA7aTx2W3NdLnNpemUoKTtpKyspCiAgICAgICAgCXsKICAgICAgICAJCWlmKCF2aXNbdltzXVtpXV0pCiAgICAgICAgCQl7CiAgICAgICAgCQkJaWYoY29sb3Jbc109PTApCiAgICAgICAgCQkJewogICAgICAgIAkJCQljb2xvclt2W3NdW2ldXT0xOwogICAgICAgIAkJCQlibGFjaysrOwogICAgICAgIAkJCX0KICAgICAgICAJCQllbHNlIGlmKGNvbG9yW3NdPT0xKQogICAgICAgIAkJCXsKICAgICAgICAJCQkJY29sb3JbdltzXVtpXV09MDsKICAgICAgICAJCQkJcmVkKys7CiAgICAgICAgCQkJIH0KICAgICAgICAJCQkgcS5wdXNoKHZbc11baV0pOwogICAgICAgIAkJCSB2aXNbdltzXVtpXV09MTsKICAgICAgICAJCX0KICAgICAgICAJfQogICAgICAgIH0KICAgICAgICBjb3V0PDwiQ2FzZSAiPDxpPDwiOiI8PCIgIjw8bWF4KHJlZCxibGFjayk8PGVuZGw7CiAgICAgICAgZm9yKGludCBpPTA7aTwyMDAwOTtpKyspCiAgICAgICAgIHZbaV0uY2xlYXIoKTsKICAgICAgICB2aXMuY2xlYXIoKTsKICAgICAgICBjb2xvci5jbGVhcigpOwogICAgIH0KCXJldHVybiAwOwp9