거대한 자동화 시설에는 N개의 작업 모듈이 있고, 일부 모듈 쌍 사이에는 정비 로봇이 지나갈 수 있는 양방향 통로가 있다. 시설 관리자는 로봇이 모든 작업 모듈을 점검할 수 있도록 통로 사용 권한을 등록하려고 한다.

각 통로를 사용하려면 해당 통로에 대한 권한을 따로 등록해야 한다. 로봇은 한 모듈에서 다른 모듈로 이동할 때 여러 모듈을 거쳐 가도 되며, 이미 점검한 모듈을 다시 지나가도 된다.

주어진 통로 정보만으로 전체 시설은 하나로 연결되어 있다. 관리자는 로봇이 모든 작업 모듈에 도달할 수 있게 하면서도, 등록해야 하는 통로 권한의 개수를 최대한 줄이고 싶다.

각 시설에 대해 필요한 통로 권한의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. T는 100 이하이다.

각 테스트 케이스는 다음 형식으로 주어진다.

• 첫 번째 줄에는 작업 모듈의 수 N과 통로의 수 M이 주어진다. N은 2 이상 1,000 이하이고, M은 1 이상 10,000 이하이다.

• 이후 M개의 줄에 a와 b가 주어진다. 이는 a번 작업 모듈과 b번 작업 모듈 사이에 양방향 통로가 있다는 뜻이다. (1 ≤ a, b ≤ N, a ≠ b)

• 주어지는 통로 정보는 항상 연결 그래프를 이룬다.

출력

테스트 케이스마다 한 줄을 출력한다.

• 로봇이 모든 작업 모듈에 도달하기 위해 등록해야 하는 통로 권한의 최소 개수를 출력한다.

예제 입력 1

2
3 3
1 2
2 3
1 3
5 4
2 1
2 3
4 3
4 5

예제 출력 1

2
4