考虑一棵无根树 $T$，它不是生物学意义上的树或植物，而是图论中具有 $n$ 个节点的无向图，节点编号从 $1$ 到 $n$。如果你不理解这里树的概念，请跳过此题。

现在我们决定用 $k$ 种不同的颜色（编号从 $1$ 到 $k$）对它的节点进行染色。对于每种颜色 $i = 1, 2, \dots, k$，定义 $E_i$ 为连接所有被染成颜色 $i$ 的节点的最小边集。如果树中没有节点被染成颜色 $i$，则 $E_i$ 为空集。

请确定一种染色方案，使得 $|E_1 \cap E_2 \cap \dots \cap E_k|$ 最大化，并输出该大小。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 1000$)，表示测试用例的总数。

对于每个测试用例，第一行包含两个正整数 $n$（树的大小）和 $k$ ($k \le 500$)（颜色的数量）。接下来的 $n-1$ 行，每行包含两个整数 $x$ 和 $y$，描述它们之间的一条边。保证给定的图是一棵树。

所有测试用例中 $n$ 的总和不超过 $200000$。

输出格式

对于每个测试用例，输出 $|E_1 \cap E_2 \cap \dots \cap E_k|$ 的最大值。

样例

输入 1

3
4 2
1 2
2 3
3 4
4 2
1 2
1 3
1 4
6 3
1 2
2 3
3 4
3 5
6 2

输出 1

1
0
1