There are $$$n$$$ cities in Byteland, some of which are connected by roads, which can be traversed in any direction. The $$$i$$$-th road has its own hardness parameter $$$w_i$$$. Time spent on traversing a road with its hardness equal to $$$w_i$$$ is $$$\lceil\frac{w_i}{c}\rceil$$$, where $$$c$$$ is the current driving skill.

The travel network of Byteland is a tree. In other words, between any pair of cities, there is exactly one path that passes through each city at most once.

In some cities you can visit driving courses. A single course takes $$$T$$$ time to complete, and after completing the course the driver's skill $$$c$$$ is increased by $$$2$$$ times. Notice that the time $$$T$$$ required to complete a course is the same in all cities, and courses can be completed in the same city more than once.

You need to answer the $$$q$$$ queries: what is the minimum time it takes to get from the city $$$a$$$ to city $$$b$$$ if you start the travelling with driving skill $$$c = 1$$$?

Input

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$T$$$ ($$$1 \le n \le 10^5, 1 \le T \le 10^6$$$) - the number of cities and time required to complete a single driving course.

The following $$$n - 1$$$ lines each contain three integers $$$u_i$$$, $$$v_i$$$ and $$$w_i$$$ ($$$1 \le u_i, v_i \le n, 1 \le w_i \le 10^6, u_i \neq v_i$$$), which mean that there exists a road connecting towns $$$u_i$$$ and $$$v_i$$$ with hardness equal to $$$w_i$$$ .

The next line contains a binary string $$$s$$$ of length $$$n$$$, consisting only of symbols $$$0$$$ and $$$1$$$. If $$$s_i = 1$$$ ($$$1 \le i \le n$$$), then you can visit driving courses in the $$$i$$$-th city. If $$$s_i = 0$$$ ($$$1 \le i \le n$$$), then you cannot visit driving courses in the $$$i$$$-th city.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries you are required to answer.

The next $$$q$$$ lines contain two integers $$$a_j$$$, $$$b_j$$$ ($$$1 \le a_j, b_j \le n, 1 \le j \le q$$$) — the cities you are required to process in the $$$j$$$-th query.

It is guaranteed that the given graph is a tree. It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each query, print one integer in a separate line — the minimum time it takes to get in the corresponding query.

Note

In the only query of the first test case, it is optimal to ignore the driving courses. Then the minimum time required is equal to the distance between vertexes $$$1$$$ and $$$2$$$, which is $$$1$$$.

In the first query of the second test case, we can spend $$$3$$$ time in city number $$$1$$$ visiting the driving courses, then go to vertex $$$5$$$. Then the minimum time required is $$$3 + \lceil\frac{5}{2}\rceil + \lceil\frac{10}{2}\rceil = 11$$$.

Teleportation in Byteland

Examples