import java.util.*;
import java.io.*;
public class Solution {
	public static void main(String[] args) throws Exception {
		FastScanner sc = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		int t = sc.nextInt();
		for(int i=1;i<=t;i++) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			gra g = new gra(n);
			for(int j=0;j<m;j++) {
				g.addEdge(sc.nextInt()-1, sc.nextInt()-1);
			}
			g.connectedComponents();
			pw.println("Case #"+i+": "+((n-(g.e-g.c)-1)*2+g.e-g.c));
		}
		pw.close();
	}
}
class gra {
    // A user define class to represent a graph.
    // A graph is an array of adjacency lists.
    // Size of array will be V (number of vertices
    // in graph)
    int V;
    int c;
    int e;
    LinkedList<Integer>[] adjListArray;
    boolean[] visited;
    // constructor
    gra(int V) {
        this.V = V;
        c=0;
        e=0;
        visited = new boolean[V];
        // define the size of array as
        // number of vertices
        adjListArray = new LinkedList[V];
        Arrays.fill(visited, true);
        // Create a new list for each vertex
        // such that adjacent nodes can be stored

        for(int i = 0; i < V ; i++){
            adjListArray[i] = new LinkedList<Integer>();
        }
    }

    // Adds an edge to an undirected graph
    void addEdge( int src, int dest) {
        // Add an edge from src to dest.
        adjListArray[src].add(dest);
        visited[src]=false;
        visited[dest]=false;
        // Since graph is undirected, add an edge from dest
        // to src also
        adjListArray[dest].add(src);
    }

    void DFSUtil(int v, boolean[] visited) {
        // Mark the current node as visited and print it
        visited[v] = true;
        e++;
        // Recur for all the vertices
        // adjacent to this vertex
        for (int x : adjListArray[v]) {
            if(!visited[x]) DFSUtil(x,visited);
        }

    }
    void connectedComponents() {
        // Mark all the vertices as not visited
        for(int v = 0; v < V; ++v) {
            if(!visited[v]) {
                // print all reachable vertices
                // from v

                DFSUtil(v,visited);
                c++;
            }
        }
    }
}
@SuppressWarnings("all")
class FastScanner {
    BufferedReader br;
    StringTokenizer st;
    public FastScanner(BufferedReader d) {
        br=d;
    }
    public FastScanner(String s) {
        try {
            br = new BufferedReader(new FileReader(s));
        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

    public FastScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String nextToken() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(nextToken());
    }

    long nextLong() {
        return Long.parseLong(nextToken());
    }

    double nextDouble() {
        return Double.parseDouble(nextToken());
    }
}