Everyone knows that at Jagiellonian University we do love plants a lot. We created hundreds of problems about trees, forests and even cacti! Unfortunately, problems about animals are not that popular. Today we want to prove that we love animals as well.

We say that a graph is a jellyfish, if it is a simple connected undirected graph with equal number of vertices and edges. You are given a jellyfish J with n vertices. For an arbitrary subset of vertices S ⊆ J, we say that S is an awesome subset if for every T ⊆ S there exists a connected subgraph of the jellyfish which contains every vertex from T and does not contain any other vertex from S.

What is the maximum possible size of an awesome subset of J?

Input

The first line contains the number of test cases z. The descriptions of the test cases follow.

The first line of each test case contains one integer n (3 ≤ n ≤ 105) - the number of vertices of the jellyfish.

The next n lines contain two integers ui, vi (1 ≤ ui ≠ vi ≤ n) each, corresponding to the jellyfish edges. It is guaranteed that the given graph is a jellyfish, and every two vertices are connected by at most one edge.

The total number of vertices in all test cases does not exceed 106.

Output

For each test case, output a single integer - the maximum possible size of an awesome subset of the jellyfish.