도시 관광

여름이면 유럽의 오래된 도시는 거리를 돌아다니며 명소를 구경하는 관광객으로 붐빈다.

오래된 도시 상당수는 설계도 없이 자연스럽게 커졌지만, 커지는 방식은 서로 비슷하다. 도시는 명소 세 곳에서 시작했고, 세 곳은 두 곳씩 짝지어 양방향 도로로 이어져 있었다. 그 뒤로 명소가 하나씩 늘어났다. 새로 생긴 명소는 이미 도로로 직접 이어져 있던 서로 다른 기존 명소 두 곳에 새 양방향 도로 두 개로 연결되었다.

이런 도시를 찾은 관광객은 되도록 많은 명소를 도는 관광 코스를 짜고 싶다. 코스는 아무 명소에서나 출발할 수 있고, 출발한 명소에서 끝나야 한다. 각 도로는 최대 한 번, 각 명소도 최대 한 번만 지난다. 출발한 명소만 예외로 정확히 두 번 지난다.

도시가 커진 과정이 주어진다. 관광 코스 하나가 지날 수 있는 서로 다른 명소의 최대 개수를 구하여라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 도시에 있는 명소의 총 개수 $N$이 주어진다. 명소에는 1번부터 $N$번까지 번호가 붙어 있다. 1, 2, 3번은 도시가 시작될 때의 명소 세 곳이고, 4번부터 $N$번까지는 도시에 추가된 순서대로 번호가 붙어 있다.

다음 $N-3$개의 줄에는 공백으로 구분된 두 정수 $A$와 $B$가 주어진다. 그 줄에 해당하는 명소가 $A$번 명소, $B$번 명소와 도로로 연결되었다는 뜻이다. 이 줄 가운데 첫 번째 줄은 4번 명소에, 두 번째 줄은 5번 명소에 대응하며, 나머지도 같은 방식이다.

제한

• $1 \le T \le 50$
• $4 \le N \le 1000$

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 테스트 케이스 번호이고 1부터 시작한다. y는 그 도시에서 관광 코스 하나가 지날 수 있는 명소의 최대 개수이다.