케이블 정리

ICPC 지역 대회 준비 중에 운영팀이 대회장에 도착하고 나서야 참가자용 컴퓨터 네트워크를 잘못 연결했다는 사실을 알았다. 컴퓨터 사이에 필요 없는 케이블이 아주 많이 설치되어 있었다.

운영 총괄 압델라흐만은 러너가 케이블에 걸려 넘어질 위험을 줄이려고 케이블을 최대한 많이 걷어내려 한다. 단, 케이블을 걷어낸 뒤에도 모든 컴퓨터가 서로 도달할 수 있어야 한다. 처음 상태에서는 모든 컴퓨터가 서로 도달할 수 있다.

두 컴퓨터를 직접 잇는 케이블이 있으면 두 컴퓨터는 서로 도달할 수 있다. 또, 두 컴퓨터가 각각 제3의 컴퓨터에서 도달할 수 있으면 그 두 컴퓨터도 서로 도달할 수 있다.

걷어낼 수 있는 케이블의 최대 개수를 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. $1 \le T \le 100$이다.

이어서 $T$개의 줄이 주어지고, 각 줄에는 공백 하나로 구분된 두 정수 $N$과 $M$이 있다. $N$은 대회장의 컴퓨터 수, $M$은 케이블 수다. $1 \le N \le 10^4$, $N - 1 \le M \le 10^5$이다.

케이블이 어느 컴퓨터를 어느 컴퓨터와 잇는지는 주어지지 않는다. 처음 상태에서 모든 컴퓨터가 서로 도달할 수 있다는 조건만 주어진다.

각 테스트 케이스마다 한 줄에 Case n: R 형식으로 출력한다. $n$은 1부터 시작하는 테스트 케이스 번호이고, $R$은 걷어낼 수 있는 케이블의 최대 개수다.