Given an weighted tree, you are to find two nodes A and B of the tree(A and B needn't to be different), such that the length of the path between A and B is less than or equals to a given integer S, and the maximum distance from each node of the tree to this path is minimum.

Input

The first line of the input contains a single integer T, the number of test cases. T blocks follow.

For each test case, the first line contains two space-separated integer N (1<=N<=100000) and S(0<=S<=100000000).N-1 lines follow, each contains three integers X(1<=X<=N), Y(1<=Y<=N) and Z(1<=Z<=1000), denotes that there is an (undirected) edge weighted Z between node X and Y. The input is correct.

Output

T lines, each contains a single integer denoted the minimum distance.

Example

Input:
2
5 2
1 2 5
2 3 2
2 4 4
2 5 3
8 6
1 3 2
2 3 2
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3
Output:
5
5