Jellyfish

Everyone knows that at Jagiellonian University we 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.

A graph is a jellyfish if it is a simple connected undirected graph with the same number of vertices and edges. You are given a jellyfish $J$ with $n$ vertices. For a subset of vertices $S \subseteq J$, call $S$ an awesome subset if for every $T \subseteq S$ there exists a connected subgraph of the jellyfish that contains every vertex of $T$ and no other vertex of $S$.

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

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 \leq n \leq 100\,000$), the number of vertices of the jellyfish.

Each of the next $n$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i \neq v_i \leq n$), describing one edge of the jellyfish. The given graph is guaranteed to be 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 $10^6$.

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