In winter, all small rivers of Al-Asi great river in Syria are frozen. But when spring comes back they start to melt. These small rivers are connected to each other exactly like a tree, each river (direct edge in the tree) has a value equal to the amount of ice in it.
Here is the tree of the sample test case:
When rivers start to melt, water starts to flow from node 1 (root of the tree) to any node that it can reach. When the water first reaches a node u, ice starts to melt in all its direct children edges at a rate of 1 unit per second. Once (u, v) edge completely melted, the rate of melting of all other edges that start from u will slow down to be 0.5 unit per second, while the other edges that start from v start melting with 1 unit per second.
Given the rivers tree, and a certain time, can you tell us how many leaves of the tree did the water reach? A leaf is a node that has no children.
The first line contains T the number of test cases. For each test case, the first line contains N the number of nodes (2 ≤ N ≤ 100, 000). Followed by N - 1 lines, each line describes the nodes 2 to N. Each line will contain 2 integers Pi and Ci (1 ≤ Pi ≤ N) (0 ≤ Ci ≤ 100,000) representing the parent of the i-th node (i starts from 2 here) and the amount of ice in the edge connecting the current node to its parent. Node 1 is the root of the tree. After that there is a line contains (1 ≤ Q ≤ 100, 000), the number of queries. Then Q lines contain the times of these queries in seconds (0 ≤ query time ≤ 1012).
Print one line for each query in each test case, this line should contain the number of leaves that the water reached at the time of the query.
1
4
1 3
1 5
2 2
8
1
2
3
4
5
6
7
8
0
0
0
0
1
1
2
2
In the sample test case:
At time 0: water is at node 1
At time 1: water has melted 1 unit of edge (1, 2), and 1 unit of edge (1, 3)
At time 3: water has completely melted edge (1, 2). The rate of melting of (1, 3) drops to 0.5 unit/second, while edge (2, 4) starts to melt at rate 1 unit/second.
At time 5: water has completely melted edge (2, 4), and the remaining edge (1, 3) has 4 units melted, 1 to go.
At time 7: Ice completely melted in all edges.
