Todo el mundo sabe que en la Universidad Jaguelónica amamos mucho las plantas. Hemos creado cientos de problemas sobre árboles, bosques e incluso cactus. Desafortunadamente, los problemas sobre animales no son tan populares. Hoy queremos demostrar que también amamos a los animales.

Decimos que un grafo es una medusa (jellyfish) si es un grafo simple, conexo y no dirigido con el mismo número de vértices y aristas. Se te da una medusa $J$ con $n$ vértices. Para un subconjunto arbitrario de vértices $S \subseteq J$, decimos que $S$ es un subconjunto asombroso si para todo $T \subseteq S$ existe un subgrafo conexo de la medusa que contiene cada vértice de $T$ y no contiene ningún otro vértice de $S$.

¿Cuál es el tamaño máximo posible de un subconjunto asombroso de $J$?

Entrada

La primera línea de la entrada contiene el número de casos de prueba $z$. A continuación siguen las descripciones de los casos de prueba.

La primera línea de cada caso de prueba contiene un entero $n$ ($3 \le n \le 100\,000$) — el número de vértices de la medusa.

Las siguientes $n$ líneas contienen dos enteros $u_i, v_i$ ($1 \le u_i \neq v_i \le n$) cada una, correspondientes a las aristas de la medusa. Se garantiza que el grafo dado es una medusa y que cada dos vértices están conectados por a lo sumo una arista.

El número total de vértices en todos los casos de prueba no excede $10^6$.

Salida

Para cada caso de prueba, imprime una sola línea que contenga un único entero: el tamaño máximo posible de un subconjunto asombroso de la medusa.

Ejemplos

Entrada 1

2
6
1 2
2 3
3 4
4 1
2 5
2 6
4
1 2
2 3
3 4
4 1

Salida 1

4
3