Description

Mr. Kuo is an adventurer. One day, he finds a special "tree".

The tree consists of N vertices. 

There are exactly one simple path between any two vertices.

 

Mr. Kuo wants to do the following operation K times to this tree：

• If the tree is empty, do nothing.
• If the tree consists of one vertex, remove this vertex.
• If the tree consists of two vertices, remove both vertices.
• Otherwise, remove all the leaf of the tree.

（A leaf of a tree is a vertex that is connected to at most one vertex.）

 

Mr. Kuo is wondering how many vertices will remain after he performs the operations K times.

 

Take the sample test as the example：

• In test case 1, {2, 4, 5, 7, 9, 12, 13} are removed and {1, 3, 6, 8, 10, 11} remain.
• In test case 2, {1, 2} are removed and no vertex remains.
• In test case 3, {1, 2, 6, 7} are removed and {3, 4, 5} remain.
• In test case 4, {2, 4, 5} are removed and {1, 3, 6} remain.
• In test case 5, no vertices are removed and {1, 2, 3} remain.

 

The picture below is the tree of the test case 4 in the sample test.

The picture below is the tree after Mr. Kuo performs the operation once.

 

Input

The first line contains one integer T — the number of test cases. Description of the test cases follows.

The first line of each test cases contains two integer N K — the number of vertices in the tree and the number of operations Mr. Kuo performs.

Each of the next N - 1 lines contains two integers u_i and v_i — there is an edge between u_i and v_i.

 

For each test：

1. T ≤ 100, N ≤ 20
2. T ≤ 100, N ≤ 100
3. T ≤ 100, N ≤ 500
4. T ≤ 100, N ≤ 1000
5. T ≤ 100, N ≤ 5000
6. T ≤ 100, N ≤ 20000

1 ≤ u_i, v_i ≤ N

0 ≤ K ≤ N for all test.

Output

For each test case print an integer — the number of verticees remain in the tree.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss