← 返回题目列表

Codeforces · 1846/A

A. 鲁道夫和割绳子

中文机器翻译题面 查看原题

墙上钉有$$$n$$$个钉子,第$$$i$$$钉子被钉在距离地面$$$a_i$$$米的位置,$$$b_i$$$米长的绳子的一端系在上面。所有的钉子都悬挂在不同的高度上。一颗糖果同时绑在所有绳子上。糖果绑在绳子的一端,绳子的一端没有绑在钉子上。

要拿走糖果,您需要将其降低到地面。为此,鲁道夫可以割断一些绳子,一次一根。帮助鲁道夫找到获得糖果所需的最少绳子数量。

下图显示了第一个测试的示例:

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$) — 钉子的数量。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le 200$$$) — 第 $$$i$$$ 钉子的高度和绑在其上的绳子的长度,所有 $$$a_i$$$ 均为不同。

保证数据不矛盾,可以构建语句中描述的配置。

输出

对于每个测试用例,打印一个整数 - 需要切断以使糖果落到地上的最小绳子数量。

示例

输入 #1

4
3
4 3
3 1
1 2
4
9 2
5 2
7 7
3 4
5
11 7
5 10
12 9
3 2
1 5
3
5 6
4 5
7 7

输出 #1

2
2
3
0