It's Sparsh (techno-cultural fest of SVNIT) time and that means a week long holidays for SVNITians!! Almost all students get their full entertainment from events in Sparsh. But there are people who stay in a group and trip in holidays.

This year again we have this kind of group who wants to go on a trip in this week long holidays. As the Sparsh dates are nearby they still haven't planned their journey. But they've made a list of places which are left for them to visit. There are N places in total numbered from 0 to N-1. They've marked all the existing routes from one place to another and this comes out to be a spanning tree.

As two weekends added up to normal fest holidays, they wanted to cover maximum places possible. But they have a hard time getting the route that connects maximum number of places. Hence, they ask you to help'em out finding the route which covers maximum places as they are excited to know how many places they are going to visit a week later. In the tour, they do not want to visit a place more than once.

Input:
First line contains T denoting the number of test cases.
Description of T test cases follows.
Each test case has N lines. First line of test case has the number N denoting number of cities they listed to visit.
Each of the rest of lines contains two integers a,b denoting there exists a direct join between cities a and b.

Output:
For each test case, print what are the maximum number of cities that are included in a single route.

Constraints:
1 <= T <= 3000
1 <= N <= 2000

Large Input files. Use fast input methods.

Problem Setter : Deepak Singh