Baches bit a bit#13103

Baches bit a bit

4 segundos
256 megabytes

Un país tiene ciudades y n - 1 carreteras bidireccionales, cada una de las cuales conecta dos ciudades distintas. La red de carreteras es conexa: se puede llegar de cualquier ciudad a cualquier otra. Por lo tanto, cualesquiera dos ciudades están unidas por exactamente una ruta, es decir, un camino que no visita ninguna ciudad dos veces.

Cada carretera tiene un número entero no negativo de baches. El presidente quiere que toda ruta entre dos ciudades distintas sea lisa. Una ruta se llama lisa si el AND bit a bit de las cantidades de baches de sus carreteras es igual a su OR bit a bit (las operaciones bit a bit se recuerdan más abajo).

Una cuadrilla de obras puede repetir la siguiente operación cualquier número de veces:

Recordemos las definiciones. El bit número de un entero no negativo es su dígito binario en la posición de 2^i (el bit es el menos significativo).

Encuentra el número mínimo de operaciones necesarias para que toda ruta entre dos ciudades distintas sea lisa.

Entrada

La primera línea contiene un único entero (1 \le t \le 10^5) — el número de casos de prueba.

La primera línea de cada caso de prueba contiene un único entero (1 \le n \le 2 \cdot 10^5) — el número de ciudades. Cada una de las siguientes n - 1 líneas contiene tres enteros , y (1 \le u, v \le n, u \ne v, 0 \le w < 2^{30}): una carretera entre las ciudades y con baches. Se garantiza que la red de carreteras es conexa.

La suma de sobre todos los casos de prueba no excede 2 \cdot 10^5.

Salida

Para cada caso de prueba imprime un entero — el número mínimo de operaciones.

Ejemplos

Ejemplo 1

Loading
Loading

Nota

En el primer caso de prueba las ciudades forman una cadena 1 - 2 - 3 - 4 - 5 con 1, 0, 0, 1 baches en sus carreteras. Basta una operación: invertir el bit en la ruta de la ciudad a la ciudad . Entonces cada carretera tiene bache.

En el segundo caso de prueba una operación en la ruta de la ciudad a la ciudad con i = 2 convierte en , y las cuatro carreteras tienen baches.

En el tercer caso de prueba solo hay una ciudad, así que no hay rutas entre ciudades distintas y no hay que hacer nada.

En el cuarto caso de prueba la cadena 1 - 2 - 3 - 4 tiene baches. Bastan tres operaciones: la ruta 1 \to 3 con i = 0, la ruta 2 \to 3 con i = 1 y la ruta 1 \to 2 con i = 2. Entonces cada carretera tiene baches.

En el quinto caso de prueba la ciudad está unida a las ciudades , y , y las carreteras 2 - 3, 4 - 5 y 6 - 7 continúan las tres ramas. Las tres carreteras que salen de la ciudad tienen baches, y las tres exteriores tienen . Bastan dos operaciones: la ruta 2 \to 4 con i = 0 y la ruta 1 \to 6 con i = 0. Entonces cada carretera tiene bache. Se puede demostrar que una operación no es suficiente.