B. Мультфильмы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Таня любит мультфильмы. В прокате ожидаются $$$n$$$ мультфильмов, и $$$i$$$-й из них будет показываться в ее любимом кинотеатре со дня $$$a_i$$$ по день $$$b_i$$$ ($$$1 \le a_i \le b_i \le 10^9$$$).

В кинотеатре действует особая акция: в любой день, в который в прокате идёт ровно один мультфильм, кинотеатр даёт существенную скидку на сеанс.

Тане не важно, какой мультфильм посмотреть, но она хочет сэкономить, поэтому просит Вас найти любой такой день $$$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$$$ строках содержатся их описания: $$$i$$$-я строка содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i \le b_i \le 10^9$$$) — период показа соответствующего мультфильма.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$2000$$$.

Выходные данные

Для каждого из $$$t$$$ наборов входных данных в порядке их записи в тесте выведите ответ. В качестве ответа на $$$i$$$-й набор выведите любое такое $$$x$$$, что в день $$$x$$$ в прокате идёт ровно один мультфильм. Если таких дней не существует, то выведите -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
500000001
-1
10
10
Примечание

Третий набор входных данных: в дни $$$1$$$ и $$$2$$$, первый и третий мультфильмы будут в прокате, а в дни $$$3$$$ и $$$4$$$ — второй и третий. Таким образом, нет такого дня, когда только один мультфильм будет в прокате.

В четвертом тесте $$$11$$$ также является возможным ответом.