题目描述

企鹅国的网吧们之间由网线互相连接，形成一棵树的结构。现在由于冬天到了，供暖部门缺少燃料，于是他们决定去拆一些网线来做燃料。

但是现在有$\red{K}$只企鹅要上网和别人联机游戏，所以他们需要把这$\red{K}$只企鹅安排到不同的机房（两只企鹅在同一个机房会吵架），然后拆掉一些网线，但是需要保证 每只企鹅至少还能通过留下来的网线和至少另一只企鹅联机游戏。

所以他们想知道，最少需要保留多少根网线？

输入格式

第一行一个整数$\red{T，}$表示数据组数；

每组数据第一行两个整数$\red{N，}$$\red{K，}$表示总共的机房数目和企鹅数目。

第二行$\red{N-1}$个整数，第$\red{i}$个整数$\red{Ai}$表示机房$\red{i+1}$和机房$\red{Ai}$有一根网线连接$\red{(1≤}$$\red{Ai≤}$$\red{i)}$。

输出格式

每组数据输出一个整数表示最少保留的网线数目。

样例

输入样例

2

4 4

1 2 3

4 3

1 1 1

输出样例

2
2

提示

数据范围

对于$\red{30\%}$的数据：$\red{N≤}$$\red{15}$；

对于$\red{50\%}$的数据：$\red{N≤}$$\red{300}$；

对于$\red{70\%}$的数据：$\red{N≤}$$\red{2000}$；

对于$\red{100\%}$的数据：$\red{2≤}$$\red{K≤}$$\red{N≤}$$\red{100000，}$$\red{T≤}$$\red{10}$。