Bitwise Potholes#13103

Bitwise Potholes

4 seconds
256 megabytes

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:

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).

Find the minimum number of operations needed to make every route between two different cities smooth.

Input

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.

Output

For each test case print one integer — the minimum number of operations.

Examples

Example 1

Loading
Loading

Note

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.