A country has cities and n - 1 two-way roads, each connecting two different cities. The road network is connected: one can get from any city to any other one. Hence any two cities are joined by exactly one route, a path that visits no city twice.
Every road has a non-negative integer number of potholes. The president wants to make every route between two different cities smooth. A route is called smooth if the bitwise AND of the numbers of potholes on its roads is equal to their bitwise OR (the bitwise operations are recalled below).
A road crew can repeat the following operation any number of times:
Choose two different cities and and an integer i \ge 0, and on every road of the route from to replace the number of potholes by w \oplus 2^i (that is, flip bit ).
Recall the definitions. Bit number of a non-negative integer is its binary digit at the position of 2^i (bit is the least significant one).
The bitwise AND of several integers has bit equal to if and only if bit equals in every one of them.
The bitwise OR of several integers has bit equal to if and only if bit equals in at least one of them.
The bitwise XOR () of two integers has bit equal to if and only if bit differs in these two integers. In particular, w \oplus 2^i is with bit flipped.
Find the minimum number of operations needed to make every route between two different cities smooth.
The first line contains a single integer (1 \le t \le 10^5) — the number of test cases.
The first line of each test case contains a single integer (1 \le n \le 2 \cdot 10^5) — the number of cities. Each of the next n - 1 lines contains three integers , and (1 \le u, v \le n, u \ne v, 0 \le w < 2^{30}): a road between cities and with potholes. It is guaranteed that the road network is connected.
The sum of over all test cases does not exceed 2 \cdot 10^5.
For each test case print one integer — the minimum number of operations.
Example 1
In the first test case the cities form a chain 1 - 2 - 3 - 4 - 5 with 1, 0, 0, 1 potholes on its roads. One operation is enough: flip bit on the route from city to city . Then every road has pothole.
In the second test case one operation on the route from city to city with i = 2 changes into , and all four roads have potholes.
In the third test case there is only one city, so there are no routes between different cities and nothing needs to be done.
In the fourth test case the chain 1 - 2 - 3 - 4 has potholes. Three operations are enough: route 1 \to 3 with i = 0, route 2 \to 3 with i = 1 and route 1 \to 2 with i = 2. Then every road has potholes.
In the fifth test case city is joined to cities , and , and the roads 2 - 3, 4 - 5 and 6 - 7 continue the three branches. The three roads at city have potholes, and the outer three have . Two operations are enough: route 2 \to 4 with i = 0 and route 1 \to 6 with i = 0. Then every road has pothole. It can be shown that one operation is not enough.