你有一个可以沿着数轴移动的机器人。在$$$0$$$时刻,它位于$$$0$$$点。
您向机器人发出 $$$n$$$ 命令:在 $$$t_i$$$ 秒处,您命令机器人前往点 $$$x_i$$$。每当机器人收到命令时,它就会开始以每秒$$$1$$$单位的速度向点$$$x_i$$$移动,并在到达该点时停止。然而,当机器人移动时,它会忽略你给他的所有其他命令。
例如,假设您向机器人发出三个命令:在时间 $$$1$$$ 移动到点 $$$5$$$,在时间 $$$3$$$ 移动到点 $$$0$$$,在时间 $$$6$$$ 移动到点 $$$4$$$。然后机器人站在$$$0$$$直到时间$$$1$$$,然后开始向$$$5$$$移动,忽略第二个命令,在$$$6$$$时间到达$$$5$$$并立即开始移动到$$$4$$$以执行第三个命令。在时间 $$$7$$$ 达到 $$$4$$$ 并停在那里。
当机器人位于点 $$$x_i$$$ 时,如果在 $$$[t_i, t_{i + 1}]$$$ 范围内(即在发出此命令之后和发出另一个命令之前,包括两个边界;我们认为 $$$t_{n + 1} = +\infty$$$)内有一个时间点,则称命令 $$$i$$$ 成功。计算成功命令的数量。请注意,被忽略的命令有可能成功。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。接下来的几行描述了测试用例。
测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 命令数量。
接下来的 $$$n$$$ 行描述命令。这些行中的第 $$$i$$$ 包含两个整数 $$$t_i$$$ 和 $$$x_i$$$ ($$$1 \le t_i \le 10^9$$$, $$$-10^9 \le x_i \le 10^9$$$) — 第 $$$i$$$ 命令的时间和点。
命令按时间排序,即对于所有可能的 $$$i$$$,$$$t_i < t_{i + 1}$$$。
测试用例 $$$n$$$ 的总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出一个整数——成功命令的数量。
示例
输入 #1
8 3 1 5 3 0 6 4 3 1 5 2 4 10 -5 5 2 -5 3 1 4 1 5 1 6 1 4 3 3 5 -3 9 2 12 0 8 1 1 2 -6 7 2 8 3 12 -9 14 2 18 -1 23 9 5 1 -4 4 -7 6 -1 7 -3 8 -7 2 1 2 2 -2 6 3 10 5 5 8 0 12 -4 14 -7 19 -5
输出 #1
1 2 0 2 1 1 0 2
注意
问题陈述中描述了第一个测试用例中机器人的运动。只有最后一个命令成功。
在第二个测试用例中,第二个命令成功:机器人在时间 $$$5$$$ 通过目标点 $$$4$$$。另外,最后一个命令最终成功了。
在第三个测试用例中,没有命令成功,机器人在 $$$7$$$ 时刻停在 $$$-5$$$ 处。
以下是示例中每个测试用例每秒机器人位置的 $$$0$$$ 索引序列。剪切后所有位置都等于最后一个:
1.$$$[0, 0, 1, 2, 3, 4, 5, 4, 4, \点]$$$
2. $$$[0, 0, 1, 2, 3, 4, 5, 5, 5, 5, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -5, \点]$$$
3.$$$[0, 0, 0, -1, -2, -3, -4, -5, -5, \点]$$$
4.$$$[0, 0, 0, 0, 1, 2, 3, 3, 3, 3, 2, 2, 2, 1, 0, 0, \点]$$$
5. $$$[0, 0, 1, 0, -1, -2, -3, -4, -5, -6, -6, -6, -6, -7, -8, -9, -9, -9, -9, -8, -7, -6, -5, -4, -3, -2, -1, -1, \点]$$$
6.$$$[0, 0, -1, -2, -3, -4, -4, -3, -2, -1, -1, \点]$$$
7.$$$[0, 0, 1, 2, 2, \点]$$$
8. $$$[0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7, -7, \点]$$$