样例下载

题目描述

你正在打游戏。

游戏从 0 时刻开始。

开始时共有 N 个敌人，编号为 1 ~ N。

对于敌人 i，他将会在时刻 Ai 结束后逃走。一旦敌人逃走，你无法再消灭他。所以你不能晚于 Ai 时刻开始打击敌人 i，并且需要持续打击 Bi 时间才能将其消灭，在将其消灭前，你不能再打击其他敌人。一旦你开始打击某个敌人，则该敌人将被你的火力控制，直至被你消灭，无法再逃走。

你可以任意选择要消灭的敌人以及消灭的顺序。问：你最多能消灭多少个敌人？

多组数据。

输入格式

第一行：一个整数 $T$，表示数据组数。

对于每组数据：

第一行：一个整数 $N$。

接下来 $N$ 行，每行两个整数 $A_i$ , $B_i$。

数据保证所有组数据 $\sum N ≤ 3×10^5$。

输出格式

共 T 行，每组数据的答案占一行。

输入样例

3
2
1 2
1 3
2
1 2
2 3
3
10 10
10 20
10 30

输出样例

1
2
2

数据范围

100% 的数据：$1 ≤ T ≤ 10, 1 ≤ N ≤ 2×10^5, 0 ≤ A_i ≤ 10^{18}, 1 ≤ B_i ≤ 10^{18}$。其中

• 10% 的数据：$1 ≤ N ≤ 10$
• 10% 的数据：每组数据内的 $B_i$ 均相等。
• 10% 的数据：$N ≤ 2000$，$A_i, B_i ≤ 2000$。
• 30% 的数据：$N ≤ 2000, 0 ≤ A_i ≤ 10^{18}, 1 ≤ B_i ≤ 10^{18}$。