K-th value

Problem Description

There is a country with N cities. These all cities are connected with roads and have no cycles. Consider all simple paths whose lengths are between L and R (both inclusive). Your task is to find the path that minimizes the k-th value of the path among them. The k-th value of a simple path is “floor(length of path / k) + 1”-th value of the sorted length list of all roads in the path.

Input

The first line contains a single integer T representing the number of test cases($1\leq T\leq 100$) Sum of all $N\leq 700000$ The first line of each test case contains a single integer N. Each of the following N – 1 lines contains 3 integers which represents two cities of the road and the length of the road. Next lines contains 3 integers k, L, R. $1\leq N \leq 10^5$ $1\leq a_i \leq 10^9$ $1 \leq L \leq R \leq 50$ $1<k<50$

Output

Output the minimum k-th value of all simple paths whose length is between L and R. If no such path exists output -1.

Sample Input

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

Sample Output

2

Author

金策工业综合大学（DPRK）

Source

2016 Multi-University Training Contest 9