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.