Sunset 得到了一张边境小镇废弃金矿的地图。地图显示，这座金矿由 $n$ 个房间和 $n-1$ 条双向隧道组成，构成了一棵树。这张地图非常奇怪，每条隧道 $i$ 上都有两个数字 $a_i$ 和 $b_i$。Sunset 只知道，恰好有 $k$ 条隧道的长度取自 $a_i$，而其余 $n-k-1$ 条隧道的长度取自 $b_i$。

明天 Sunset 将去探索这座金矿。他担心在金矿中迷路，所以你能告诉他，如果他足够幸运，金矿的直径是多少吗？换句话说，请根据 Sunset 已知的信息，计算直径的最小可能长度。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10\,000$)，表示测试用例的数量。每个测试用例：

第一行包含两个整数 $n$ 和 $k$ ($2 \le n \le 20\,000, 0 \le k \le n-1, k \le 20$)，分别表示房间数量和参数 $k$。

接下来的 $n-1$ 行，每行包含四个整数 $u_i, v_i, a_i, b_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le a_i, b_i \le 10^9$)，表示 $u_i$ 号房间和 $v_i$ 号房间之间有一条双向隧道，其长度为 $a_i$ 或 $b_i$。

保证所有 $n$ 的总和不超过 $200\,000$。

输出格式

对于每个测试用例，输出一行，包含一个整数：直径的最小可能长度。

样例

输入 1

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

输出 1

6