描述

在现代的魔术表演中，穿越墙壁非常流行，魔术表演者可以在预设的舞台上穿越多个墙壁。墙壁穿越者有有限的穿墙能量，每次表演最多能穿越 k 道墙壁。墙壁被布置在一个类似网格的区域中。一个例子如图 1 所示，从上方看地面。所有的墙壁宽度为 $1$，但长度不同。你可以假设没有一个网格单元属于两道或更多的墙壁。观众选择一个网格的列。我们的墙壁穿越者从网格的上方开始，沿着整个列走，穿越沿途的每道墙壁，直到到达网格的下方。如果他在尝试走某列时遇到超过$k$ 道墙壁，他将无法展示一个好的表演。例如，在图 1 所示的墙壁配置中，一个能穿越最多 $3$ 道墙壁的穿越者可以选择任何一列，除了第 $6$ 列。

给定一个墙壁穿越者和一个舞台，要求我们移除最少数量的墙壁，以便让我们的表演者能从观众选择的任何一列开始，穿越所有的墙壁。

输入

输入文件的第一行包含一个整数 $t$ ($1 <= t <= 10$)，表示测试用例的数量，接着是每个测试用例的输入数据。每个测试用例的第一行包含两个整数 $n$ ($1 <= n <= 100$)，表示墙壁的数量，以及 $k$ ($0 <= k <= 100$)，表示墙壁穿越者最多能穿越的墙壁数量。接下来有 $n$ 行，每行包含两个 $(x, y)$ 坐标对，表示墙壁的两个端点的坐标。坐标是小于或等于 $100$ 的非负整数。网格的左上角假定为坐标 $(0, 0)$。以下是一个示例测试用例，对应于图 1 中给出的地面。

输出

对于每个测试用例，输出一行，包含一个整数，表示移除的最少墙壁数量，以便墙壁穿越者可以从上方的任何一列开始穿越墙壁。

2
3 1
2 0 4 0
0 1 1 1
1 2 2 2
7 3
0 0 3 0
6 1 8 1
2 3 6 3
4 4 6 4
0 5 1 5
5 6 7 6
1 7 3 7

1
1

提示

墙壁与 X 轴平行。

来源

Tehran 2002 Preliminary