题目描述

小悠最近迷上了一款平面射击小游戏。

游戏的规则很简单：弹弓固定在原点 $(0,0)$ 处，每次可以朝第一象限射出一只弹丸，弹丸的飞行轨迹一定形如 $y=ax^2+bx$，其中 $a,b$ 由玩家指定，且必须满足 $a \lt 0$，$a,b$ 均为实数。弹丸落回地面（$x$ 轴）时立刻消失。

某个关卡里，第一象限中站着 $n$ 只绿猪，第 $i$ 只位于 $\left(x_i,y_i \right)$。若某次发射的轨迹经过 $\left( x_i, y_i \right)$，这只绿猪就被消灭，弹丸则沿原轨迹继续飞行；若轨迹不经过该点，本次发射对它毫无影响。

举个例子：若两只绿猪分别在 $(1,3)$ 与 $(3,3)$，发射一条 $y=-x^2+4x$ 的轨迹就能把它们一并消灭。

游戏目标就是消灭所有绿猪。每个关卡还带有一个神秘指令类型 $m$（见【输入格式】），部分指令会给关卡附加特殊的性质。

游戏共有 $T$ 个关卡。小悠想知道：每个关卡至少要发射多少只弹丸，才能消灭全部绿猪？

输入格式

第一行包含一个正整数 $T$，表示关卡总数。

下面依次输入 $T$ 个关卡。每个关卡第一行包含两个非负整数 $n,m$，分别表示绿猪数量与神秘指令类型。接下来 $n$ 行，第 $i$ 行包含两个正实数 $x_i,y_i$，表示第 $i$ 只绿猪的坐标。保证同一关卡中不存在两只坐标完全相同的绿猪。

如果 $m=0$，表示该指令没有任何作用。

如果 $m=1$，则该关卡满足：至多用 $\lceil n/3 + 1 \rceil$ 只弹丸即可消灭所有绿猪。

如果 $m=2$，则该关卡满足：一定存在一种最优解，其中有一只弹丸消灭了至少 $\lfloor n/3 \rfloor$ 只绿猪。

保证 $1\leq n \leq 18$，$0\leq m \leq 2$，$0 \lt x_i,y_i \lt 10$，输入中的实数均保留到小数点后两位。

上文中，符号 $\lceil c \rceil$ 与 $\lfloor c \rfloor$ 分别表示对 $c$ 向上、向下取整，例如：$\lceil 2.1 \rceil = \lceil 2.9 \rceil = \lceil 3.0 \rceil = \lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3$。

输出格式

对每个关卡依次输出一行答案。

每行包含一个正整数，表示该关卡消灭所有绿猪最少需要的弹丸数量。

样例

2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00

1
1

3
2 0
1.41 2.00
1.73 3.00
3 0
1.11 1.41
2.34 1.79
2.98 1.49
5 0
2.72 2.72
2.72 3.14
3.14 2.72
3.14 3.14
5.00 5.00

2
2
3

1
10 0
7.16 6.28
2.02 0.38
8.33 7.78
7.68 2.09
7.46 7.86
5.77 7.44
8.24 6.72
4.42 5.11
5.42 7.79
8.15 4.99

6

提示

【样例解释 1】

这组数据共两个关卡。第一个关卡即题目描述中的情形，两只绿猪位于 $(1.00,3.00)$ 与 $(3.00,3.00)$，一条 $y=-x^2+4x$ 即可全灭。第二个关卡的 $5$ 只绿猪坐标都在抛物线 $y=-x^2+6x$ 上，同样只需一只弹丸。

【数据范围】