import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

  private static final int MAX_SIZE = 20000;

  private static void bfs(int v, List<Integer>[] g, BitSet used, BitSet color, int[] sizes) {
    Deque<Integer> q = new LinkedList<>();
    q.addLast(v);
    used.set(v);
    while (!q.isEmpty()) {
      v = q.removeFirst();
      ++sizes[color.get(v) ? 1 : 0];
      for (int to: g[v]) {
        if (!used.get(to)) {
          used.set(to);
          color.set(to, !color.get(v));
          q.addLast(to);
        }
      }
    }
  }

  public static void main(String[] args) {
    InputReader in = new InputReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    int t = in.nextInt(), n, u, v;
    for (int k = 1; k <= t; ++k) {
      System.gc();
      BitSet used = new BitSet(MAX_SIZE);
      BitSet arr = new BitSet(MAX_SIZE);
      BitSet color = new BitSet(MAX_SIZE);
      n = in.nextInt();
      List<Integer>[] g = new ArrayList[MAX_SIZE];
      for (int i = 0; i < MAX_SIZE; ++i) g[i] = new ArrayList<>();
      while (n-- > 0) {
        u = in.nextInt() - 1;
        v = in.nextInt() - 1;
        arr.set(u);
        arr.set(v);
        g[u].add(v);
        g[v].add(u);
      }

      int ans = 0;
      for (int i = 0; i < MAX_SIZE; ++i) {
        if (!used.get(i) && arr.get(i)) {
          int[] sizes = {0, 0};
          bfs(i, g, used, color, sizes);
          ans += Math.max(sizes[0], sizes[1]);
        }
      }
      out.println("Case " + k + ": " + ans);
    }
    out.close();
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public long nextLong() {
      return Long.parseLong(next());
    }
  }
}