Andy's dream has always been to be the mayor of a city. To realize his dream, he has decided to build his own city: Andyville. He builds buildings in Andyville and since he is a programmer, he connects them with a super efficient road system. In fact, each of the buildings in his town is connected to every other building through exactly one unique route (which means that there are no circular routes).
After building his city, Andy realizes that as a result of his efficient system, driving around his city is incredibly arduous: routes are often incredibly long and involve lots of U-turns. Giving into the complaints of his citizens, Andy decides to build another road so that a circular route is formed. Find the length of the longest circular route that he can make.
The first line of the input provides the number of test cases, . test cases follow. Each test case begins with an integer . lines follow, each containing two integers signifying that a road exists between buildings and .
Note: For of the cases, .
For each test case, your program should output one integer: the length of the longest circular route he can make by creating a new road between two buildings.
2 3 1 2 1 3 5 1 2 1 3 1 4 4 5
Explanation for Sample
In the first test case, connecting buildings and forms a circular route that contains three buildings . In the second case, connecting buildings and would result in a circular route of four buildings . Connecting buildings and would also result in a circular route of length .