G. Road Trip
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are $$$n$$$ cities in Treeland, connected by bidirectional roads. It is possible to travel from any city to any other city, but only in a single way. In other words, the road network of Treeland forms a tree.

You are planning a road trip around Treeland. Your car has a tank capacity of $$$c$$$ liters. For each road, you know how much fuel is required to pass through it. The car can be refueled in any city, but there are no gas stations between the cities. The fuel is cheap in Treeland, so you only want to minimize the number of refueling stops to have more time admiring Treeland's scenic routes.

You are not sure which route to take yet. Answer $$$q$$$ queries of the form: given two cities $$$u$$$ and $$$v$$$, how many times do you need to refuel when traveling from the city $$$u$$$ to the city $$$v$$$? Assume that you start in the city $$$u$$$ with a full tank.

Input

The first line of input contains the number of test cases $$$Z$$$ ($$$1 \leq Z \leq 10\,000$$$). The descriptions of the test cases follow.

The first line of a test case contains three integers $$$n$$$, $$$q$$$, and $$$c$$$ ($$$2 \leq n \leq 200\,000$$$, $$$1 \leq q \leq 200\,000$$$, $$$1 \leq c \leq 10^9$$$) – the number of cities, the number of queries, and the tank capacity respectively.

The next $$$n-1$$$ lines describe the road network. Each line contains integers $$$a_i$$$, $$$b_i$$$ and $$$w_i$$$ ($$$a_i \neq b_i, 1 \leq a_i, b_i \leq n$$$, $$$1 \leq w_i \leq c$$$) – the endpoint cities and the required fuel amount for the $$$i$$$-th road.

The final $$$q$$$ lines describe the queries. Each line contains two distinct integers $$$u_j$$$ and $$$v_j$$$ ($$$u_j \neq v_j, 1 \leq u_j, v_j \leq n$$$) – the queried pair of cities.

The sum of $$$n$$$ over all test cases does not exceed $$$400\,000$$$. The sum of $$$q$$$ over all test cases does not exceed $$$400\,000$$$.

Output

For each query, print a single line containing the minimum possible number of refuelings.

Example
Input
1
7 6 5
1 2 3
2 3 3
2 4 1
1 5 2
5 6 1
6 7 4
3 6
3 7
4 6
4 7
3 4
7 1
Output
2
2
1
2
0
1
Note

For the first query in the sample, one of the optimal routes is as follows:

  • start in city $$$3$$$ with a full tank with $$$5$$$ liters of fuel;
  • drive to city $$$2$$$ using $$$3$$$ liters of fuel, bringing the tank's fuel down to $$$2$$$ liters;
  • refuel the car, bringing the tank up to $$$5$$$ liters of fuel again;
  • drive to city $$$1$$$ using $$$3$$$ liters and bringing the tank's fuel down to $$$2$$$ liters;
  • drive to city $$$5$$$ using our $$$2$$$ remaining liters of fuel;
  • refuel the car for the last time;
  • drive to city $$$6$$$ using only one liter out of the five remaining in the tank.