El Prof. Pang y el Prof. Shou disfrutan jugando a un juego de persecución.

El mapa del juego consiste en $n$ habitaciones y $n - 1$ canales bidireccionales. El mapa del juego es conexo. Esto significa que el mapa forma un árbol.

Al principio, el Prof. Pang está en la habitación $u$, mientras que el Prof. Shou está en la habitación $v$ ($u \neq v$). El Prof. Pang y el Prof. Shou juegan por turnos, y el Prof. Shou mueve primero. En su turno, el jugador conoce su propia posición y la posición del otro jugador, y puede decidir quedarse en la habitación actual o moverse a otra habitación que esté conectada directamente con la actual mediante un canal. Cuando el Prof. Pang y el Prof. Shou están en la misma habitación, el Prof. Shou es atrapado por el Prof. Pang.

El Prof. Pang y el Prof. Shou son lo suficientemente inteligentes. El Prof. Pang quiere atrapar al Prof. Shou en un número finito de turnos. El Prof. Shou no quiere ser atrapado por el Prof. Pang en ningún número finito de turnos.

El Prof. Shou se cansa de ser atrapado cada vez y busca la ayuda del Prof. Fei. El Prof. Shou le pide al Prof. Fei que añada algunos canales para que el Prof. Pang no pueda atraparlo en un número finito de turnos para cualquier par de habitaciones iniciales $(u, v)$. El Prof. Fei es perezoso, por lo que espera añadir la menor cantidad de canales posible. Si, sin importar cómo se añadan los canales, siempre existe un par de habitaciones $(u, v)$ tal que el Prof. Pang puede atrapar al Prof. Shou, imprima $-1$.

Entrada

La primera línea contiene un único entero $T$ ($1 \leq T \leq 10^4$) que denota el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un único entero $n$ ($2 \leq n \leq 10^5$) que denota el número de habitaciones.

Para las siguientes $n - 1$ líneas, cada línea contiene dos enteros $u$ y $v$ ($1 \leq u, v \leq n$) que denotan un canal que conecta la habitación $u$ y la habitación $v$.

Se garantiza que la suma de $n$ sobre todos los casos de prueba no excede $2 \times 10^5$, y que las habitaciones y los canales siempre forman un árbol.

Salida

Para cada caso de prueba, imprima un número que denote la cantidad mínima de canales añadidos, o simplemente imprima $-1$.

Ejemplos

Entrada 1

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

Salida 1

-1
1
-1
2