# Paths on the Tree

Time Limit: 6 Seconds

Memory Limit: 131072 KB

## Description

Edward has a tree with n vertices conveniently labeled with 1,2,…,n.

Edward finds a pair of paths on the tree which share no more than k common vertices. Now Edward is interested in the number of such ordered pairs of paths.

Note that path from vertex a to b is the same as the path from vertex b to a. An ordered pair means (A, B) is different from (B, A) unless A is equal to B.

## Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains two integers n, k (1 ≤ n, k ≤ 88888). Each of the following n - 1 lines contains two integers ai, bi, denoting an edge between vertices ai and bi (1 ≤ ai, bin).

The sum of values n for all the test cases does not exceed 888888.

## Output

For each case, output a single integer denoting the number of ordered pairs of paths sharing no more than k vertices.

## Sample Input

1
4 2
1 2
2 3
3 4


## Sample Output

93


## Hint

The number of path pairs that shares no common vertex is 30.

The number of path pairs that shares 1 common vertex is 44.

The number of path pairs that shares 2 common vertices is 19.

path A paths share 2 vertices with A total
1-2-3-4 1-2, 2-3, 3-4 3
1-2-3 1-2, 2-3, 2-3-4 3
2-3-4 1-2-3, 2-3, 3-4 3
1-2 1-2, 1-2-3, 1-2-3-4 3
2-3 1-2-3, 1-2-3-4, 2-3, 2-3-4 4
3-4 1-2-3-4, 2-3-4, 3-4 3

None