Given a tree, you need to count how many subtrees with diameter ≤ K exist.

Input

The first line contains the number of test cases T. T test cases follow. For each test case, the first line contains N and K. The following N - 1 lines contain two integers ai and bi, indicating an edge between nodes ai and bi in the tree. There is a blank line after each test case.

Output

Output T lines, one corresponding to each test case, containing the required answer.

Example

Input:
2
3 1
0 1
1 2
6 3
0 1
1 2
2 3
2 4
3 5
Output:
5
23

Constraints

1 ≤ T ≤ 100
2 ≤ N ≤ 60
0 ≤ ai, bi < N
1 ≤ K ≤ N - 1