All Tracks Algorithms Graphs Breadth First Search Problem

Acfreak was working on a tree problem which he finds hard to solve. So he called upon you to help him out to solve the task. You are given an undirected weighted tree rooted at 1. You need to count the number of distinct paths from the root to leaves such that the XOR-Value of the weights in the path is odd. 

Input

Assume that Acfreak was working on $$T$$ different trees. For each tree, you will be given an integer $$N$$ that denotes the total number of nodes. The next $$N-1$$ lines contain three integers $$a_i,b_i,c_i$$ which denote that there is an edge between the nodes $$a_i$$ and $$b_i$$ with weight $$c_i$$.

Output

In a separate line, print the count of distinct paths satisfying the requirement.

Constraints
\(1 \le T \le 10 \\ 1 \le N \le 10^5 \\ 1 \le a_i, b_i \le N\\ w_i \in {0,1}\)