In a quaint forest, a magnificent tree with \(N\) vertices, each connected by \(N-1\) enchanting edges where each edge has some value.
The goal is to count the number of simple paths having the following intriguing properties:

The number of set bits (1's) in the Bitwise XOR result of all the edge values on the simple path is even.
The length of the simple path is odd (i.e., the count of edges in the simple path is odd).

Note: A simple path is a path in a tree that does not have repeating vertices. A simple path from node u to node v is considered different than a simple path from node v to node u.

Input format

The first line contains a single integer \(T\), which denotes the number of test cases.
For each test case:
- The first line contains \(N\) denoting the number of vertices in the tree.
- The following \(N-1\) lines contain 3 space-separated integers, \(u\), \(v\), and \(w\) indicating that there is an edge between vertices \(u\) & \(v\), and this edge has value \(w\).

Output format

For each test case, print the number of simple paths having the aforementioned intriguing properties in a new line.

Constraints

\(1 \leq T \leq 10^5 \\ 3 \leq N \leq 10^6 \\ 1≤u,v≤N\\ 0≤w≤10^9 \\ \text{The sum of all values of N over all test cases doesn't exceed } 10^6 \)