제설차

어느 도시의 시청은 해마다 그랬듯 겨울에 당황하고 싶지 않아서 벌써부터 내년 제설 계획을 세우고 있다.

계획의 핵심은 현대식 제설차를 사는 것이다. 시청은 일부 교차로에 있는 차고에 제설차를 배치한다. 준비할 시간이 넉넉하므로 제설차는 어느 교차로에나 세워 둘 수 있다.

제설을 할 때가 되면 제설차는 도로를 따라 달리기만 하면 된다. 모든 도로는 양방향이며, 제설차의 폭이 매우 넓어서 한 번만 지나가면 그 도로는 제설이 끝난다. 작업을 마친 제설차는 출발한 교차로로 돌아갈 필요 없이 곧바로 아무 차고로나 들어간다.

제설차를 사는 것만으로 끝이 아니라 연료도 필요하다. 교차로에서 차고로 들어갈 때 드는 연료는 무시할 만큼 적으므로, 한 제설차가 쓰는 연료는 그 제설차가 달린 도로의 수와 같다. 따라서 모든 도로를 각각 정확히 한 번씩만 달릴 때 전체 연료가 최소가 된다.

이렇게 연료를 가장 적게 쓰는 계획들 중에서, 모든 도로를 제설하려면 제설차가 최소 몇 대 필요한가?

첫 줄에는 테스트 집합의 개수를 나타내는 자연수 $Z$ ($Z = 1$) 가 주어진다. 이어서 각 테스트 집합이 주어진다.

각 테스트 집합의 첫 줄에는 두 자연수 $n$ ($1 \le n \le 100000$) 과 $m$ ($1 \le m \le 1000000$) 이 주어지며, 각각 교차로의 수와 도로의 수를 뜻한다. 다음 $m$ 개의 줄에는 서로 다른 두 자연수 $a$ 와 $b$ ($1 \le a, b \le n$) 가 주어지며, 교차로 $a$ 와 $b$ 를 잇는 도로를 나타낸다. 도로는 양방향이고, 같은 두 교차로를 잇는 도로가 여러 개일 수 있다.

각 테스트 집합마다 한 줄에 자연수 $L$ 하나를 출력한다. $L$ 은 연료를 가장 적게 쓰면서(즉 모든 도로를 정확히 한 번씩만 달리면서) 모든 도로를 제설할 수 있는 제설차의 최소 대수이다.

연료를 가장 적게 쓰는 것은 모든 도로를 정확히 한 번씩만 달릴 때이므로, 모든 도로를 $L$ 개의 경로로 나누어 각 도로가 정확히 한 경로에만 속하고 각 경로가 도로를 따라 이어지는 연속된 이동이 되도록 해야 한다. 이때 가능한 가장 작은 $L$ 을 출력한다.