Tracking Communities in social networks, like facebook, twitter etc, are one of the most exiting works in the field of Artificial Intelligence now-a-days. A community is a group of people who are connected. Two persons are connected and form a community if they are directly connected or connected via some other persons. That means if person A and B are connected and B and C are also connected then A and C are connected and they all belong to the same community. It is quite obvious that, one single person can also form a community by himself.

Now you are given a description of a community where there are n persons and the connections between some pairs of the persons. You can assume that they do form a community and their connection is given such that if you want to find two persons' connectivity information, you will find exactly one path between them.

Now maintaining a connection between a pair requires some cost. And unfortunately, the social networking site cannot afford keeping a community which requires a cost of more than K. For example, say A and B and B and C are connected and cost(A, B) = 5, cost(B, C) = 2. Then if K ≥ 7, they can afford this community. Otherwise they cannot.

So, they have made a plan, and that is they will break the community. They want to break the community into multiple communities such that each community requires maintenance cost of no more than K. But if there are too many communities people may leave the network, that's why they want the minimum number of communities. Since you are the best, they find no option but to ask you.

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing two integers n (1 ≤ n ≤ 100) and K (1 ≤ K ≤ 100). Each of the next n - 1 lines contains three integers u v w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 100, u ≠ v) meaning that there is a connection between person u and v and the maintenance cost of this connection is w.

For each case, print the case number and the minimum number of communities they have to maintain.