← 返回题目列表

Codeforces · 1610/C

C. 克氏正在举办派对

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

Keshi 正在举办一个聚会,他希望聚会中的每个人都开心。

他有 $$$n$$$ 个朋友。他的第 $$$i$$$ 个朋友拥有 $$$i$$$ 美元。

如果你邀请第 $$$i$$$ 个朋友参加聚会,只有当聚会中至多 $$$a_i$$$ 人严格比他富有并且最多 $$$b_i$$$ 人严格比他贫穷时,他才会高兴。

Keshi 希望邀请尽可能多的人。找出他可以邀请参加聚会的最多人数,以便每个被邀请的人都会高兴。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(1\le n\le 2 \cdot 10^5)$$$ — Keshi 的朋友数量。

以下 $$$n$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ $$$(0 \le a_i, b_i < n)$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印 Keshi 可以邀请的最大人数。

示例

输入 #1

3
3
1 2
2 1
1 1
2
0 0
0 1
2
1 0
0 1

输出 #1

2
1
2

注意

在第一个测试用例中,他邀请了第一个人和第二个人。如果他邀请所有人,第三个人不会高兴,因为会有超过 $$$1$$$ 的人比他穷。