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.
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 the minimum k-th value of all simple paths whose length is between L and R.
If no such path exists output -1.