전장

전장은 도시 $N$개와 양방향 도로 $R$개로 이루어진다. 원하는 도시 $C$ 하나를 골라 출발해서 모든 도로를 정확히 한 번씩 지나고 다시 $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 15$

각 테스트 케이스마다 한 줄에 Case #x: 를 출력하고, 그 뒤에 새로 놓아야 하는 도로의 최소 개수를 출력한다. $x$는 테스트 케이스 번호다.