There are N cities in a country. The roads between the cities form a binary Tree with the cities. Two tourists A and B start at the same city (which can be any city). They want to arrive at two cities such that the distance of the cities is as large as possible. Please find the distance.

Note that all the length of the road is always 1. And when you calculate the distance, one road can be calculated at most once.

First line is an integer T, which is the number of test cases. (1 <= T <= 50)

For each test case, there will be an integer in a single line N (1 <= N <= 10000). N is the number of nodes. The nodes are numbered from 1 to N.

Then there will be N – 1 lines with two integer x, y for each line. (1 <= x, y <= N)

x y means x is the farther of y. What’s more, we guarantee the input file is a tree. And the children are labeled from left to right by the order they appear.

For each test case, print the largest distance problem required.

Hard problem.