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

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<ll>vl;
typedef vector<vi>vii;
typedef vector<vl>vll;
typedef pair<int,int>pii;
typedef double dl;
typedef pair<dl,dl>pdd;
typedef pair<ll,ll>pll;

#define PB push_back
#define F first
#define S second
#define MP make_pair
#define nl '\n'
#define all(a)(a).begin(),(a).end()
#define sz(x) (int)x.size()
#define REP(i,m,n) for(int i=m;i<n;i++)

const double PI = acos(-1);
const double eps = 1e-9;

#define mem(a,b) memeset(a,b,sizeof(a))
#define gcd(a,b) __gcd(a,b)
#define sqr(a) ((a)*(a))
#define prof ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fraction(a) cout.unsetf(ios::floatfield); cout.precision(a);cout.setf(ios::fixed,ios::floatfield);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
const int mx=20100;
vector<int>adj[mx];
int color[mx];
bool visited[mx];
int cnt1=0,cnt2=0;
bool dfs(int node,int col)
{
    visited[node]=true;
    color[node]=col;
    if (col == 1) cnt1++;
    else cnt2++;
    for(auto u:adj[node])
    {
        if(visited[u]==false)
        {
            bool f=dfs(u,col==1?2:1);
            if(!f)
                return false;
        }
        else
        {
            if(color[node]==color[u])
                return false;
        }

    }
    return true;
}
int main()
{
    prof;
    int tc;
    cin>>tc;
    int cnt3=1;
    while(tc--)
    {
        int m;
        cin>>m;
        int cnt=0;
        for (int i = 1; i < mx; ++i) adj[i].clear();
        for (int i = 1; i < mx; ++i) visited[i] = false;
        for(int i=0; i<m; i++)
        {
            int u,v;
            cin>>u>>v;
            cnt=max(cnt,max(u,v));
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        int res = 0;
        for(int i=1; i<=cnt; i++)
        {
            if(visited[i]==false) {
				cnt1 = 0, cnt2 = 0;
				dfs(i,1);
				if (cnt1 == 0 or cnt2 == 0) cnt1 = 0, cnt2 = 0;
				res += max(cnt1,cnt2);
			}
        }
        cout<<"Case "<<cnt3<<": "<<res<<nl;
        cnt3++;
    }

    return 0;
}