Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 153428/153428 K (Java/Others)


There is a tree having N vertices. In the tree there are K monkeys (K <= N). A vertex can be occupied by at most one monkey. They want to remove some edges and leave minimum edges, but each monkey must be connected to at least one other monkey through the remaining edges.
Print the minimum possible number of remaining edges.


The first line contains an integer T (1 <= T <= 100), the number of test cases.
Each test case begins with a line containing two integers N and K (2 <= K <= N <= 100000). The second line contains N-1 space-separated integers $a_1, a_2, …, a_{N-1}$, it means that there is an edge between vertex $a_i$ and vertex i+1 (1 <= $a_i$ <= i).


For each test case, print the minimum possible number of remaining edges.

Sample Input

2 4 4 1 2 3 4 3 1 1 1

Sample Output

2 2




2017 Multi-University Training Contest - Te