전장의 도로 놓기

전장은 도시 $N$개와 양방향 도로 $R$개로 이루어져 있다. 원하는 도시 $C$ 하나를 골라 출발해서 $R$개의 도로를 각각 정확히 한 번씩 지난 뒤 다시 $C$로 돌아오는 것이 목표다.

그런 이동이 불가능하면 도로를 새로 놓아 가능하게 만들어야 하고, 새로 놓는 도로의 개수는 최소여야 한다. 같은 두 도시를 잇는 도로가 여러 개 있을 수 있다. 새 도로는 서로 다른 두 도시 사이라면 어디든 놓을 수 있고, 이미 도로가 있는 두 도시 사이에도 다시 놓을 수 있다.

각 테스트 케이스마다 새로 놓아야 하는 도로의 최소 개수를 구한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어지고, 각 테스트 케이스는 다음과 같다.

• 한 줄에 도시의 수 $N$
• 한 줄에 도로의 수 $R$
• 도로를 나타내는 $R$개의 줄. 각 줄에는 그 도로의 두 끝 도시 $A$와 $B$가 공백 하나로 구분되어 주어진다. $A$와 $B$는 서로 다른 정수이고 $0 \le A, B < N$이다.

제한

• $1 \le T \le 30$
• $2 \le N \le 1000$
• $1 \le R \le 10^4$

각 테스트 케이스마다 한 줄에 Case #x: 를 먼저 출력하고, 그 뒤에 새로 놓아야 하는 도로의 최소 개수를 출력한다. 여기서 $x$는 테스트 케이스 번호로 1부터 시작한다.