Tiptoe through the tulips

All submissions for this problem are available.

Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.

Cherry has discovered the Garden of Magical Tulips while going on a walk. The garden can be described as N nodes connected by N-1 trails. The nodes are numbered from 1 to N. Each trail i connects two different nodes, u_i and v_i and has length L_i. It is possible to visit all the nodes starting from any node using a sequence of trails.

Magical tulips like to grow alone, without being disturbed. So, every node has exactly one tulip growing there peacefully and a tulip never withers once it is fully grown. If a fully grown tulip is picked, a new one will grow in the same spot if it is left undisturbed for X contiguous days.

Sometimes, when Cherry goes for a walk, she visits the garden to collect some tulips for her beloved Jimma, who is always waiting at the window to see Cherry pass by. The number of tulips she collects on a particular day depends on her mood. She gets bored while walking on long trails, so on day d_j, Cherry will start at a node u_j and visit all the nodes she can reach while taking only the trails whose length does not exceed k_j. She will pick all the fully grown tulips she can find. But in the process, she might visit some nodes which do not have a fully grown tulip yet. These tulips will get upset and grow fully only after X days if Cherry doesn't disturb them again before that.

i.e. if Cherry does not visit that node again before the day d_j+X, then it will have a fully grown tulip on that day. On day d₁, all the nodes have fully grown tulips.

Cherry has never been to school and is not very good at counting, so she always wonders how many tulips she has collected. Please help Cherry figure out the number of tulips she collects for the next Q days she visits the garden.

Input

• The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer N. The next N-1 lines describe the edges. The i+1^th line contains three space separated integers u_i, v_i and L_i.
• The next line contains two space separated integers Q and X and is followed by Q lines each describing the next Q days Cherry visits the garden. The j^th such line contains three space separated integers d_j, u_j and k_j.

Output

• For each test case, output Q lines.
• The j^th line of each test case should contain the number of tulips Cherry collects on day d_j.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N,Q ≤ 10⁵
• 1 ≤ u_i,v_i ≤ N
• 1 ≤ L_i,k_j ≤ 10⁸
• 1 ≤ d₁ ≤ 10⁸
• d_j-1 < d_j ≤ 10⁸ for 2 ≤ j ≤ Q

Subtasks

• Subtask 1: X = 1 (15 points)
• Subtask 2: 1 ≤ X ≤ 10⁸ (85 points)

Example

Input:
1
3 
1 2 7
3 1 10
3 4
5 2 8
7 1 20
13 2 3

Output:
2
1
1

Explanation

Example case 1. There are 3 queries. The tulips take 4 days to grow fully. In the first query, Cherry will visit nodes 1 and 2, because the trail 3-1 has length greater than 8. Both the nodes will have fully grown tulips. After Cherry picks them, the tulips will grow back on day 5+4, if Cherry doesn't visit them again. So the output is 2.

In the second query, Cherry will visit all the trails because all of them have length less than 20. The tulips at 1,2 haven't grown back yet and now all the tulips will take 4 more days. There is a tulip at 3. So the output is 1.

In the third query, on day 13, all the tulips have grown back, but Cherry will not use any of the trails because both of them have length greater than 3. So, she will collect only one tulip - the tulip at 2.