City Tour

In summer, the old cities of Europe fill up with tourists who wander the streets and visit points of interest.

Many old cities grew on their own rather than from a plan, and yet they grew in much the same way. A city started from three points of interest, with each pair joined by a bidirectional street. After that, points of interest were added one at a time. Each new point was joined by two new bidirectional streets to two different earlier points that were already directly connected by a street.

A tourist visiting such a city wants a tour that takes in as many points of interest as possible. The tour may start at any point of interest and must end at that same point. It uses each street at most once and each point of interest at most once. The starting point is the one exception, and it is visited exactly twice.

You are given how the city grew. Find the largest number of different points of interest that a single tour can visit.

The first line contains the number of test cases $T$. $T$ test cases follow.

Each test case begins with the integer $N$, the total number of points of interest in the city. Points are numbered from 1 to $N$. Numbers 1, 2, and 3 are the three original points the city started from, and numbers 4 through $N$ are the other points in the order they were added.

The next $N-3$ lines each contain two space-separated integers $A$ and $B$, meaning that the point belonging to that line was joined by streets to point $A$ and point $B$. The first of these lines belongs to point 4, the second to point 5, and so on.

Limits

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

For each test case, print one line in the form "Case #x: y". Here x is the test case number, counting from 1, and y is the largest number of points of interest a tour can visit in that city.