Pretty Diabolical

TRAOMBINNAA is going to be Billy Butcher's base for the next season of the boys. He is going to build a forest around it to fool Homlander in case of any attack. As Homlander has weakness staring at similar looking objects, Butcher will build the forest with several $K$-beautiful trees.

Now, you’re given a tree consisting of n nodes. Find the number of nodes needed to make the tree $K$-beautiful, or state that it’s impossible so that Butcher can put away that tree. You can select any node as the root node in this problem. Recall that a tree is a connected acyclic undirected graph with n nodes and $n-1$ edges. A $K$-beautiful tree is such that at least one of its child node has distance $K$ from the root and all other child with distance from root less than or equal to $K$. Note that a tree can have several beautiful configurations considering different root node. For clear understanding, look at the given pictures below.

Input

Input starts with $T$ ($1 ≤ T ≤ 10^{5}$), the number of test cases. The first line of each test case consists of two integers, $N$ ($1 ≤ N ≤ 10^{5}$) and $K$ ($1 ≤ K ≤ 10^{18}$), the number of nodes in the tree and the required beautiful configuration. Each of the next $N-1$ lines consists of two integers $a$ and $b$ ($1 ≤ a, b ≤ N$), denoting an edge between node $a$ and node $b$.

Sum of $N$ over all test cases does not exceed $10^{5}$.

Output

for each test case, print the minimum number of nodes needed to be added to the tree for making it a $K$-beautiful tree. If it’s impossible to build a $K$-beautiful tree, print “-1” (w/o quotes).

Sample

Input	Output
2 7 1 1 2 1 3 1 4 4 5 4 6 6 7 7 7 4 5 4 6 6 7 2 1 3 1 1 4	-1 3