Problem Description

CRB has a tree, whose vertices are labeled by 1, 2, …, $N$. They are connected by $N$ – 1 edges. Each edge has a weight.
For any two vertices $u$ and $v$(possibly equal), $f(u, v)$ is xor(exclusive-or) sum of weights of all edges on the path from $u$ to $v$.
CRB’s task is for given $s$, to calculate the number of unordered pairs $(u, v)$ such that $f(u, v)\ =\ s$. Can you help him?

Input

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains an integer $N$ denoting the number of vertices.
Each of the next $N$ - 1 lines contains three space separated integers $a$, $b$ and $c$ denoting an edge between $a$ and $b$, whose weight is $c$.
The next line contains an integer $Q$ denoting the number of queries.
Each of the next $Q$ lines contains a single integer $s$.
1 ≤ $T$ ≤ 25
1 ≤ $N$ ≤ $10^{5}$
1 ≤ $Q$ ≤ 10
1 ≤ $a$, $b$ ≤ $N$
0 ≤ $c$, $s$ ≤ $10^{5}$
It is guaranteed that given edges form a tree.

Output

For each query, output one line containing the answer.

1
3
1 2 1
2 3 2
3
2
3
4

1
1
0

Hint

For the first query, (2, 3) is the only pair that f(u, v) = 2.
For the second query, (1, 3) is the only one.
For the third query, there are no pair (u, v) such that f(u, v) = 4.

Author

KUT（DPRK）