#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int T, N, M;
int *deg;
vector<int> *edge;

int main()
{
cin >> T;
for (int i = 1; i <= T; i++)
{
cin >> N >> M;
deg = new int[N + 1];
edge = new vector<int>[N + 1];

for (int j = 1; j <= N; j++)
deg[j] = 0;

for (int j = 0; j < M; j++)
{
int x, y;
cin >> x >> y;
deg[x]++;
deg[y]++;
edge[x].push_back(y);
edge[y].push_back(x);
}

for (int j = 1; j <= N; j++)
{
if (deg[j] == 2)
{
int x = edge[j][0];
int y = edge[j][1];
int xsize = edge[x].size();
int ysize = edge[y].size();
for (int k = 0; k < xsize; k++)
{
if (edge[x][k] == y)
{
edge[j].erase(edge[j].begin(), edge[j].end());

vector<int>::iterator it;

it = find(edge[x].begin(), edge[x].end(), j);
edge[x].erase(it);

it = find(edge[y].begin(), edge[y].end(), j);
edge[y].erase(it);

deg[j] = 0;
deg[x]--;
deg[y]--;

j = min(min(x, y), j) - 1;
break;
}
}
}
}

int cnt = 0;
for (int j = 1; j <= N; j++)
if (deg[j] != 0)
cnt++;

cout << "Case #" << i << endl;
cout << cnt << endl;

delete[] deg;
delete[] edge;
}

return 0;

}



73점 시간초과...