//08/06/2019
#include<bits/stdc++.h>
 
using namespace std;
 
#define debug printf("Debug\n");
#define ll long long
#define ull unsigned long long
#define pi acos(-1.0)
#define mod 1000000007
 
#define _fastio  ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define in_freopen  freopen("in.txt", "r", stdin);
#define out_freopen freopen("out.txt", "w", stdout);
 
set<ll>st;
vector<ll>graph[200005];
ll level[200005],parent[200005],ev,od;
 
 
void dfs(ll src,ll par){
    ll len=graph[src].size();
    for(ll i=0;i<len;i++){
        ll adj=graph[src][i];
        if(adj==par)
            continue;
        //cout<<adj<<src<<endl;
        level[adj]=level[src]+1;
        parent[adj]=src;
        dfs(adj,src);
    }
}
 
void querydfs(ll src,ll par){
    ll len=graph[src].size();
    for(ll i=0;i<len;i++){
        ll adj=graph[src][i];
        if(adj==par)
            continue;
        if(level[adj]%2==0)
            ev++;
        else
            od++;
        querydfs(adj,src);
    }
}
 
void Ini(){
    for(ll i=0;i<100005;i++){
        graph[i].clear();
        level[i]=0;
        parent[i]=0;
    }
    //memset(level,0,sizeof(level));
    //memset(parent,0,sizeof(parent));
}
 
int main(){
    ll nodes,edges,t;
 
    scanf("%lld",&t);
 
    for(ll z=1;z<=t;z++){
        Ini();
        st.clear();
        scanf("%lld",&edges);
        for(ll i=1;i<=edges;i++){
            ll u,v;
            scanf("%lld %lld",&u,&v);
            graph[u].push_back(v);
            graph[v].push_back(u);
            st.insert(u);
            st.insert(v);
        }
 
        ll ans=0;
        auto it=st.begin();
 
        while(it!=st.end()){
            if(level[*it]==0){
                level[*it]=1;
                ev=0,od=1;
                dfs(*it,parent[*it]);
                querydfs(*it,parent[*it]);
                ans+=max(ev,od);
            }
            it++;
        }
        printf("Case %lld: %lld\n",z,ans);
    }
    return 0;
}

Ly8wOC8wNi8yMDE5CiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBkZWJ1ZyBwcmludGYoIkRlYnVnXG4iKTsKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSB1bGwgdW5zaWduZWQgbG9uZyBsb25nCiNkZWZpbmUgcGkgYWNvcygtMS4wKQojZGVmaW5lIG1vZCAxMDAwMDAwMDA3CgojZGVmaW5lIF9mYXN0aW8gIGlvc19iYXNlOjogc3luY193aXRoX3N0ZGlvKGZhbHNlKTsgY2luLnRpZSgwKTsgY291dC50aWUoMCk7CiNkZWZpbmUgaW5fZnJlb3BlbiAgZnJlb3BlbigiaW4udHh0IiwgInIiLCBzdGRpbik7CiNkZWZpbmUgb3V0X2ZyZW9wZW4gZnJlb3Blbigib3V0LnR4dCIsICJ3Iiwgc3Rkb3V0KTsKCnNldDxsbD5zdDsKdmVjdG9yPGxsPmdyYXBoWzIwMDAwNV07CmxsIGxldmVsWzIwMDAwNV0scGFyZW50WzIwMDAwNV0sZXYsb2Q7CgoKdm9pZCBkZnMobGwgc3JjLGxsIHBhcil7CiAgICBsbCBsZW49Z3JhcGhbc3JjXS5zaXplKCk7CiAgICBmb3IobGwgaT0wO2k8bGVuO2krKyl7CiAgICAgICAgbGwgYWRqPWdyYXBoW3NyY11baV07CiAgICAgICAgaWYoYWRqPT1wYXIpCiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIC8vY291dDw8YWRqPDxzcmM8PGVuZGw7CiAgICAgICAgbGV2ZWxbYWRqXT1sZXZlbFtzcmNdKzE7CiAgICAgICAgcGFyZW50W2Fkal09c3JjOwogICAgICAgIGRmcyhhZGosc3JjKTsKICAgIH0KfQoKdm9pZCBxdWVyeWRmcyhsbCBzcmMsbGwgcGFyKXsKICAgIGxsIGxlbj1ncmFwaFtzcmNdLnNpemUoKTsKICAgIGZvcihsbCBpPTA7aTxsZW47aSsrKXsKICAgICAgICBsbCBhZGo9Z3JhcGhbc3JjXVtpXTsKICAgICAgICBpZihhZGo9PXBhcikKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgaWYobGV2ZWxbYWRqXSUyPT0wKQogICAgICAgICAgICBldisrOwogICAgICAgIGVsc2UKICAgICAgICAgICAgb2QrKzsKICAgICAgICBxdWVyeWRmcyhhZGosc3JjKTsKICAgIH0KfQoKdm9pZCBJbmkoKXsKICAgIGZvcihsbCBpPTA7aTwxMDAwMDU7aSsrKXsKICAgICAgICBncmFwaFtpXS5jbGVhcigpOwogICAgICAgIGxldmVsW2ldPTA7CiAgICAgICAgcGFyZW50W2ldPTA7CiAgICB9CiAgICAvL21lbXNldChsZXZlbCwwLHNpemVvZihsZXZlbCkpOwogICAgLy9tZW1zZXQocGFyZW50LDAsc2l6ZW9mKHBhcmVudCkpOwp9CgppbnQgbWFpbigpewogICAgbGwgbm9kZXMsZWRnZXMsdDsKCiAgICBzY2FuZigiJWxsZCIsJnQpOwoKICAgIGZvcihsbCB6PTE7ejw9dDt6KyspewogICAgICAgIEluaSgpOwogICAgICAgIHN0LmNsZWFyKCk7CiAgICAgICAgc2NhbmYoIiVsbGQiLCZlZGdlcyk7CiAgICAgICAgZm9yKGxsIGk9MTtpPD1lZGdlcztpKyspewogICAgICAgICAgICBsbCB1LHY7CiAgICAgICAgICAgIHNjYW5mKCIlbGxkICVsbGQiLCZ1LCZ2KTsKICAgICAgICAgICAgZ3JhcGhbdV0ucHVzaF9iYWNrKHYpOwogICAgICAgICAgICBncmFwaFt2XS5wdXNoX2JhY2sodSk7CiAgICAgICAgICAgIHN0Lmluc2VydCh1KTsKICAgICAgICAgICAgc3QuaW5zZXJ0KHYpOwogICAgICAgIH0KCiAgICAgICAgbGwgYW5zPTA7CiAgICAgICAgYXV0byBpdD1zdC5iZWdpbigpOwoKICAgICAgICB3aGlsZShpdCE9c3QuZW5kKCkpewogICAgICAgICAgICBpZihsZXZlbFsqaXRdPT0wKXsKICAgICAgICAgICAgICAgIGxldmVsWyppdF09MTsKICAgICAgICAgICAgICAgIGV2PTAsb2Q9MTsKICAgICAgICAgICAgICAgIGRmcygqaXQscGFyZW50WyppdF0pOwogICAgICAgICAgICAgICAgcXVlcnlkZnMoKml0LHBhcmVudFsqaXRdKTsKICAgICAgICAgICAgICAgIGFucys9bWF4KGV2LG9kKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBpdCsrOwogICAgICAgIH0KICAgICAgICBwcmludGYoIkNhc2UgJWxsZDogJWxsZFxuIix6LGFucyk7CiAgICB9CiAgICByZXR1cm4gMDsKfQ==

MTAKNTIKNDMgNTEKMjcgMTMKNjcgMzIKNTAgOQoxMyAzMgo3NCAxMAo3IDEKMTcgOAo0NiA0NAo3MCA1CjI0IDEKNzYgMzYKMzIgNgo3OCAyOQoyMyAzMwo3NCAyCjU3IDI0CjgwIDE1CjMwIDIxCjI3IDIzCjQ3IDMyCjY5IDIKNTQgMTAKNjggMjUKNzAgOAozIDE4CjIyIDE2CjI5IDYKNjAgOQo3NiAyMQo3NCAxNQoxOCAyMQoxNCAxCjYyIDIKMTUgMTIKNTQgMTMKMjAgNgo4IDEKNjggMTQKNjIgMTMKMjggMwo4MCA1CjUyIDYKNTEgMwozNiA4CjEgNQozMCAxCjggMwozNyAyCjMxIDMKNTMgMgo2IDEKMzkKNDEgMjUKMzkgMTgKMjUgMjEKNiA4CjUyIDI2CjE4IDI1CjIgMjQKNDkgMTUKMTcgMjIKMjkgMjUKNDQgMjAKMTAgMjIKMjggMTQKMjggMgoyNiAyMwozIDYKMjMgMgoyNCA5CjE5IDEwCjE0IDEzCjQwIDMKMzggMwozMyAxNAo2NyAzCjIyIDEyCjQzIDMKNTEgMTIKNjIgOQoxNyA1CjUxIDkKNjMgMwo2MyA1CjY5IDcKOSA1CjQzIDUKMjIgMgo2NSAxCjMgMgo2NCAxCjQxCjM5IDgKMzcgMzMKMzggMjUKNyA4CjMwIDIxCjQ5IDMyCjQgMjAKMTMgMjcKMzQgMTUKMzIgMjEKMTUgMzEKMjkgMTkKNDIgMTgKMTggNAozIDE3CjMzIDIyCjQ4IDMKMjUgMTIKNTcgNQo0NCA2CjQxIDIwCjIwIDgKMyA5CjM5IDQKMiAxMAozNSAxNgo1MSA0CjEyIDIKNDQgOAo0NiAxMgoxOSA0CjEzIDkKMjYgNQozNSA0CjQ4IDcKNCAyCjIzIDUKNDcgMgo1MyAyCjQ1IDIKMjAgMQo1MwozNCAxMwo2NiA0Nwo5MyAzNwo4NyAzNwo0NSAyMAo5OSA0NgoyNCA2CjM2IDcKMzUgMQoyNSAzMwo4MSAxOAoyIDMKNDkgMTYKMTUgMTQKNDcgOQo1NSAxMgo2OCAzMQo5NSAxOQo0MCAyMgo1NyAxNgozNCAyOQo5NyAyNgoxOSAyNgoxMiA4Cjc3IDgKODIgNwozNyA1CjEzIDE0CjI2IDE1Cjg3IDkKODEgMTYKNDEgMTkKNTQgMwo0IDIwCjgwIDgKMzQgMQoxMDIgMTIKMzkgMgo2NiAyCjEwIDExCjk5IDExCjEyIDkKMzcgMTAKNjMgNAoxOCAyCjg3IDEKNCA3CjMwIDIKOTcgMgo3MiAxCjIyIDMKNjEgMQo2NyAxCjExCjEgOQoyMCAyCjkgMwo0IDUKMTQgNwoyMiA0CjIyIDIKMyAyCjE3IDEKMTUgMgo0IDEKMzMKMjkgMjIKMTAgNAoyOSAzMAo0MyAyNwozNCA2CjEgNgoxIDEyCjE1IDE3CjIzIDI0CjM5IDUKNDggMTEKMjIgMjEKMTIgOQo0NiAyCjM5IDQKNDYgMTcKMzggMgozNSA4CjYgMgoxNiAxMwozOCAxCjEzIDUKMTUgMgo1IDcKMzEgNgo2IDMKMzcgNQo0NSA0CjE0IDEKMjggMwo1IDEKMzUgMgozMiAxCjEyCjMgNAoxMiA0CjE0IDcKNSA5CjcgOAo2IDMKMTQgNgo4IDQKNSAxCjggMQoxMCAxCjEyIDEKNTgKNTAgMzcKMjAgMTEKMTYgMzMKMjIgMTQKNTEgNTMKNTcgOAoyNyA0CjI0IDQ4CjE0IDM0CjI4IDMwCjM1IDM3CjU1IDcKMTAgMjcKNTUgMzUKMTAgMjAKMzAgNwoyNyAxMwo3MCA3CjM5IDMwCjEyIDMKMiAxCjYyIDMwCjQ0IDkKNjkgMjgKNDQgNwoyNiAyOQo2NSAxMAo1NiAyNgoyOCAzCjQ2IDE4CjU3IDE1CjU4IDE2CjEzIDE3CjI0IDEKMjEgMTcKMzAgNAo2NyAyMQoxIDIxCjUzIDE0CjIwIDkKMTggMTIKMzUgMTUKMzMgOAo0MCA5CjUgMTQKMjAgMgo1MCA4CjY5IDEwCjcxIDIKNzAgOQoxMSA4CjIyIDIKOCAyCjQ5IDUKMzIgMwo5IDMKNSAyCjU4IDEKMTcKMjQgMwo5IDEyCjMgOQoyNCAxMgoyOSAxCjIyIDUKMzAgNgoxNiAxMAoxMCAyCjYgNAoxMiAxCjIzIDYKMTYgNQoxOCAyCjI3IDMKMiAxCjI4IDEKMjkKNDggMjQKMTYgMwozOSAyNwoxNCA3CjUxIDE2CjM4IDE5CjU0IDEwCjQ3IDEyCjI5IDgKNDggNgo1NyAxNQoyOCAxCjIwIDgKNDEgMTIKNTIgNAo0OSAxMgo0IDEwCjM0IDMKNDQgNwoxNyA4CjM5IDQKMTUgNwo1NSA0CjUwIDYKMjggMwoxMSA0CjQ0IDEKMjMgMQo1MyAxCg==

10
52
43 51
27 13
67 32
50 9
13 32
74 10
7 1
17 8
46 44
70 5
24 1
76 36
32 6
78 29
23 33
74 2
57 24
80 15
30 21
27 23
47 32
69 2
54 10
68 25
70 8
3 18
22 16
29 6
60 9
76 21
74 15
18 21
14 1
62 2
15 12
54 13
20 6
8 1
68 14
62 13
28 3
80 5
52 6
51 3
36 8
1 5
30 1
8 3
37 2
31 3
53 2
6 1
39
41 25
39 18
25 21
6 8
52 26
18 25
2 24
49 15
17 22
29 25
44 20
10 22
28 14
28 2
26 23
3 6
23 2
24 9
19 10
14 13
40 3
38 3
33 14
67 3
22 12
43 3
51 12
62 9
17 5
51 9
63 3
63 5
69 7
9 5
43 5
22 2
65 1
3 2
64 1
41
39 8
37 33
38 25
7 8
30 21
49 32
4 20
13 27
34 15
32 21
15 31
29 19
42 18
18 4
3 17
33 22
48 3
25 12
57 5
44 6
41 20
20 8
3 9
39 4
2 10
35 16
51 4
12 2
44 8
46 12
19 4
13 9
26 5
35 4
48 7
4 2
23 5
47 2
53 2
45 2
20 1
53
34 13
66 47
93 37
87 37
45 20
99 46
24 6
36 7
35 1
25 33
81 18
2 3
49 16
15 14
47 9
55 12
68 31
95 19
40 22
57 16
34 29
97 26
19 26
12 8
77 8
82 7
37 5
13 14
26 15
87 9
81 16
41 19
54 3
4 20
80 8
34 1
102 12
39 2
66 2
10 11
99 11
12 9
37 10
63 4
18 2
87 1
4 7
30 2
97 2
72 1
22 3
61 1
67 1
11
1 9
20 2
9 3
4 5
14 7
22 4
22 2
3 2
17 1
15 2
4 1
33
29 22
10 4
29 30
43 27
34 6
1 6
1 12
15 17
23 24
39 5
48 11
22 21
12 9
46 2
39 4
46 17
38 2
35 8
6 2
16 13
38 1
13 5
15 2
5 7
31 6
6 3
37 5
45 4
14 1
28 3
5 1
35 2
32 1
12
3 4
12 4
14 7
5 9
7 8
6 3
14 6
8 4
5 1
8 1
10 1
12 1
58
50 37
20 11
16 33
22 14
51 53
57 8
27 4
24 48
14 34
28 30
35 37
55 7
10 27
55 35
10 20
30 7
27 13
70 7
39 30
12 3
2 1
62 30
44 9
69 28
44 7
26 29
65 10
56 26
28 3
46 18
57 15
58 16
13 17
24 1
21 17
30 4
67 21
1 21
53 14
20 9
18 12
35 15
33 8
40 9
5 14
20 2
50 8
69 10
71 2
70 9
11 8
22 2
8 2
49 5
32 3
9 3
5 2
58 1
17
24 3
9 12
3 9
24 12
29 1
22 5
30 6
16 10
10 2
6 4
12 1
23 6
16 5
18 2
27 3
2 1
28 1
29
48 24
16 3
39 27
14 7
51 16
38 19
54 10
47 12
29 8
48 6
57 15
28 1
20 8
41 12
52 4
49 12
4 10
34 3
44 7
17 8
39 4
15 7
55 4
50 6
28 3
11 4
44 1
23 1
53 1