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$$$ 的人比他穷。