Tanya 喜欢卡通。她知道 $$$n$$$ 新动画片将在他最喜欢的电影院上映:其中 $$$i$$$ 将从 $$$a_i$$$ 日到 $$$b_i$$$ 日播出 ($$$1 \le a_i \le b_i \le 10^9$$$)。
电影院有优惠:每天只播放一部动画片,就有很大的折扣。
Tanya 不在乎她会看哪部动画片,但她想省一些钱。这就是为什么她要求您找到只有一部动画片播出的任何一天 $$$x$$$。形式上:找到 $$$x$$$,使得恰好存在一个 $$$i$$$ ($$$1 \le i \le n$$$) 和 $$$a_i \le x \le b_i$$$。如果有多个可能的答案,请打印其中任何一个。如果没有这一天,则打印-1。
输入
第一行包含单个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。以下是 $$$t$$$ 测试用例的描述。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2000$$$) — 卡通片的数量。
在接下来的 $$$n$$$ 行中,每行一个卡通片本身由一对整数 $$$a_i$$$、$$$b_i$$$ ($$$1 \le a_i \le b_i \le 10^9$$$) 描述 - 第 $$$i$$$ 卡通片的第一个和最后一个播出日。
保证输入中所有测试用例的值 $$$n$$$ 的总和不超过 $$$2000$$$。
输出
按照给定测试用例在输入中出现的顺序打印 $$$t$$$ 答案:第 $$$i$$$ 个答案是这样的 $$$x$$$,即只有一部动画片会在 $$$x$$$ 日播出,如果没有这样的日子,则为 -1。
示例
输入 #1
5 1 1 1 3 2 1000000000 2 500000000 500000002 1000000000 3 1 2 3 4 1 4 2 4 11 4 9 3 1 5 10 10 1 5
输出 #1
1 500000001 -1 10 10
注意
在第三个测试用例中:在$$$1$$$和$$$2$$$天,将播放第一部和第三部动画片,在$$$3$$$和$$$4$$$天,将播放第二部和第三部动画片。所以,没有一天只播放一部动画片。
在第四个测试用例中,$$$11$$$ 也是一个可能的答案。