Battlefield

A battlefield is made of $N$ cities and $R$ bidirectional roads. You want to pick any city $C$ you like, start there, travel every road exactly once, and finish back at $C$.

If no such trip exists, you build new roads. A new road also has to be travelled exactly once during the trip. Find the smallest number of new roads that makes the trip possible.

Several roads may connect the same pair of cities. You may build a new road between any two different cities, whether or not a road already connects them. A city that no road touches does not have to be visited.

The first line contains the number of test cases $T$. $T$ test cases follow, each in this form.

• One line with the number of cities $N$.
• One line with the number of roads $R$.
• $R$ lines, one per road. Each line has two integers $A$ and $B$ separated by one space, the two endpoints of that road. $A$ and $B$ are different and satisfy $0 \le A, B < N$.

Limits

• $1 \le T \le 30$
• $2 \le N \le 1000$
• $1 \le R \le 15$

For each test case, print one line with Case #x: followed by the smallest number of new roads. $x$ is the number of the test case.