City Tour (Small)

In summer, old European cities fill with tourists who walk the streets and visit points of interest.

Many of these cities grew without an architectural plan, and still their growth follows one pattern. A city started from three points of interest, and every pair of them was 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 wants a tour that visits as many points of interest as possible. The tour may start at any point of interest and must end at the same point. It may use each street at most once and may visit each point of interest at most once. The starting point is the only exception, and it is visited exactly twice.

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

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

Each test case begins with a line holding 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 denote the three original points, and numbers 4 to $N$ denote the other points in the order they were added.

Each of the next $N-3$ lines contains two space separated integers $A$ and $B$, meaning that the corresponding point was connected by streets to point $A$ and point $B$. The first of these lines describes point 4, the second describes point 5, the third describes point 6, and so on.

Limits

• $1 \le T \le 50$
• $4 \le N \le 15$
• $A \ne B$, and points $A$ and $B$ are already directly connected by a street at the moment the new point is added.

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