题目描述

奶牛 Bessie 有 $N$（$1\le N\le 2\cdot 10^5$）个工作需要你去完成。第 $i$ 个工作，如果你选择完成它，必须在时刻 $s_i$ 或之前开始，花费 $t_i$ 时间才能完成（$0\le s_i\le 10^{18}, 1\le t_i\le 10^{18}$）。

你可以完成的工作的最大数量是多少？时间从时刻 $0$ 开始，并且一旦你开始一个工作，你必须一直工作直到完成，而不能在此期间开始完成其他工作。

输入格式

输入的第一行包含 $T$，为测试用例的数量（$1\le T\le 10$）。每个测试用例的格式如下。 第一行包含 $N$。

以下 $N$ 行，每行包含两个整数 $s_i$ 和 $t_i$。第 $i+1$ 行为第 $i$ 个工作的信息。

输入保证所有测试用例的 $N$ 之和不超过 $3\cdot 10^5$。

输出格式

对于每个测试用例输出一行，包含你可以完成的工作的最大数量。

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

1
2
2

提示

对于第一个测试用例，你只能完成其中一个工作。在完成一个工作后，将会是时刻 $2$ 或更晚，因此已经太晚，无法开始另一个工作，必须要在时刻 $1$ 或更早才能开始。

对于第二个测试用例，你可以在时刻 $0$ 开始第二个工作并于时刻 $2$ 完成，然后在时刻 $2$ 开始第一个工作并于时刻 $5$ 完成。

• 测试点 $2$：同一个测试用例中的所有 $t_i$ 均相等。
• 测试点 $3\sim 4$：$N\le 2000$，$s_i, t_i\le 2000$。
• 测试点 $5\sim 8$：$N\le 2000$。
• 测试点 $9\sim 16$：没有额外限制。