There is a tree which contains n nodes, of course it has n - 1 edges, with weight.

Now the problem is, finding the number of (a, b) that the exclusive-xor sum of the edges between a to b is zero. Note that (a, b) is equal to (b, a).

Since the answer is very large, output it after module 1000, 000, 007.

Input starts with an integer T (T <= 10) denoting the number of test case.
For each case, first line contains n (1 <= n <= 50000) denoting the number of node, next n - 1 lines following, each line contains three
integers u, v and w (1 <= u, v <= n, 0 <= w <= 10000) which means there is an edge between u and v whose weight is w.
You can assume that the input data is valid.

For each case, output the answer after module 1000, 000, 007.