도시 관광 (작은 입력)

여름이면 유럽의 오래된 도시는 거리를 걸으며 명소를 찾는 관광객으로 붐빈다.

이런 도시 상당수는 설계도 없이 자라났지만 자라난 방식은 서로 비슷하다. 도시는 명소 세 곳에서 시작했고, 세 곳은 두 곳씩 서로 양방향 도로로 이어져 있었다. 그 뒤로 명소가 하나씩 늘어났다. 새 명소는 이미 도로로 직접 이어져 있던 서로 다른 두 명소와 각각 새 양방향 도로로 연결되었다.

관광객은 되도록 많은 명소를 도는 관광 코스를 짜려고 한다. 코스는 아무 명소에서나 출발할 수 있고, 출발한 명소로 반드시 돌아와야 한다. 같은 도로는 최대 한 번만 지날 수 있고, 같은 명소도 최대 한 번만 방문할 수 있다. 출발한 명소만 정확히 두 번 방문한다.

도시가 자라난 과정이 주어진다. 코스 하나가 방문할 수 있는 서로 다른 명소의 최대 개수를 구하라.

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

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

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

제한

• $1 \le T \le 50$
• $4 \le N \le 15$
• $A \ne B$이고, 새 명소가 추가되는 시점에 $A$번 명소와 $B$번 명소는 이미 도로로 직접 이어져 있다.

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