Gozz is wanting to open a haunted house containing rooms and halls. He has finished building the rooms and some of the halls, but is not yet done with his haunted house, since it might not have a spooky tour yet, which will be defined later. Rooms are connected by halls, which can be traversed in either direction. Gozz has made sure that every room can be reached from every other room using the existing set of halls he has built. Halls can connect a room to itself, since this is extra scary. Also, there may be multiple halls between some pair of rooms. Gozz can build new hallways between any pairs of rooms. Further, Gozz calls a tour that begins at some room, visits every hall exactly once (it may visit rooms multiple times), and finishes at the starting room, a spooky tour. He wants to make sure his haunted house has a spooky tour.

Can you help Gozz by finding the minimum number of new halls he will need to build to ensure a spooky tour exists?

Input Specification

The first line contains an integer \(T\), the number of test cases to follow. The first line of a test case contains two integers, \(N\) and \(M\), the number of rooms and existing hallways respectively. The next \(M\) lines each contain two integers \(u\) and \(v\) (\(1 \leq u,v \leq N\)) indicating that rooms \(u\) and \(v\) are connected by some hallway.

Output Specification

For each each test case, output a single line containing a single integer. The minimum number of new hallways Gozz must build to ensure a spooky tour exists.

Bounds

Note this problem includes sub-problems of increasing difficulty worth different numbers of points:

• 40 points: \(1 \leq N,M \leq 6\)
• 100 points: \(1 \leq N,M \leq 2000\)

For all sub-problems:

\(1 \leq T \leq 10\)

Sample Input

3
1 0
4 3
1 2
2 3
3 4
4 3
1 2
3 2
2 4

Sample Output

0
1
2