Roots change, but the tree stands strong — so should your logic.

Behruzbek received a tree$$$^{\text{∗}}$$$ with $$$n$$$ nodes. For a chosen root$$$^{\text{†}}$$$ $$$r$$$, Behruzbek wants to find cuteness of the tree.

Consider every set of $$$k$$$ distinct nodes of the tree. For each such set, compute its lowest common ancestor (LCA) in the tree when it is rooted at $$$r$$$. Let $$$S_r$$$ be the set of all distinct nodes obtained this way; then cuteness of the tree is $$$|S_r|$$$, where $$$|S|$$$ means the number of distinct elements.

After discovering the cuteness of trees, Behruzbek became interested in finding the kawaiiness of the tree! Kawaiiness is defined as:

$$$$$$ \sum_{r = 1}^{n} |S_r| = |S_1| + |S_2| + \dots + |S_n| $$$$$$

Unfortunately, Behruzbek is feeling sleepy now. Please help Behruzbek by finding the kawaiiness of the tree!

$$$^{\text{∗}}$$$A tree is a connected graph without cycles.

$$$^{\text{†}}$$$A rooted tree is a tree where one vertex is special and called the root.

Input

The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^{4}$$$).

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq k \leq n \leq 2\cdot 10^{5}$$$) — the number of vertices in the tree and the number of distinct integers to be chosen.

The following $$$n-1$$$ lines of each test case describe the tree. Each of the lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq n$$$, $$$u \ne v$$$) that indicate an edge between vertex $$$u$$$ and $$$v$$$. It is guaranteed that these edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^{5}$$$.

Output

For each test case, output one integer — the value of $$$\sum\limits_{r=1}^n |S_r|$$$.

Note

Let $$$f(i) = |S_i|$$$

For the third example:

Root is $$$1$$$, only $$$1$$$ and $$$2$$$ nodes can be obtained. For example, we can choose: $$$LCA(4, 5, 6) = 1$$$ and $$$LCA(2, 4, 5) = 2$$$. As a result, $$$f(1) = 2$$$.
Root is $$$2$$$, only $$$1$$$ and $$$2$$$ nodes can be obtained. For example, we can choose: $$$LCA(1, 3, 6) = 1$$$ and $$$LCA(1, 4, 5) = 2$$$. As a result, $$$f(2) = 2$$$.
Root is $$$3$$$, $$$f(3) = 3$$$. For example, node $$$3$$$ can be obtained by choosing: $$$LCA(2, 4, 6) = 3$$$.
Root is $$$4$$$, $$$f(4) = 3$$$. For example, node $$$2$$$ can be obtained by choosing: $$$LCA(1, 3, 5) = 2$$$.
Root is $$$5$$$, $$$f(5) = 3$$$. For example, node $$$2$$$ can be obtained by choosing: $$$LCA(3, 4, 6) = 2$$$.
Root is $$$6$$$, $$$f(6) = 4$$$. For example, node $$$3$$$ can be obtained by choosing: $$$LCA(3, 4, 5) = 2$$$.

Overall, $$$2 + 2 + 3 + 3 + 3 + 4 = 17$$$.

Idx	Name	Rating
A	Square?	800
B	Your Name	800
C	Isamatdin and His Magic Wand!	800
D	Yet Another Array Problem	1000
E	khba Loves to Sleep!	1600
F	Tree, TREE!!!	1600
G	Mukhammadali and the Smooth Array	1600

Codeforces Round 1062 (Div. 4)