import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*
* @author Jeel Vaishnav
*/
public class Solution {
public static void main
(String[] args
) { InputReader in = new InputReader(inputStream);
CherriesMesh solver = new CherriesMesh();
int testCount
= Integer.
parseInt(in.
next()); for (int i = 1; i <= testCount; i++)
solver.solve(i, in, out);
out.close();
}
static class CherriesMesh {
ArrayList<Integer>[] adj;
int[] vis;
void dfs(int i) {
vis[i] = 1;
for (int j : adj[i]) {
if (vis[j] == 0)
dfs(j);
}
}
public void solve
(int testNumber, InputReader sc,
PrintWriter out
) { int n = sc.nextInt();
int m = sc.nextInt();
for (int i = 0; i < n; ++i)
adj[i] = new ArrayList<>();
for (int i = 0; i < m; ++i) {
int u = sc.nextInt() - 1;
int v = sc.nextInt() - 1;
adj[u].add(v);
adj[v].add(u);
}
vis = new int[n];
int comp = 0;
for (int i = 0; i < n; ++i) {
if (vis[i] == 0) {
dfs(i);
comp++;
}
}
int red = comp - 1;
int black = n - 1 - red;
int ans = black + red * 2;
out.println("Case #" + testNumber + ": " + ans);
}
}
static class InputReader {
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private InputReader.SpaceCharFilter filter;
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
}
while (!isSpaceChar(c));
return res * sgn;
}
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
}
while (!isSpaceChar(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
return readString();
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
}