D. Прыжки по отрезкам
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп разрабатывает уровень для игры. Уровень состоит из $$$n$$$ отрезков на числовой прямой, $$$i$$$-й отрезок начинается в точке с координатой $$$l_i$$$ и заканчивается в точке с координатой $$$r_i$$$.

Игрок начинает уровень в точке с координатой $$$0$$$. За один ход он может переместиться на любую точку, расстояние до которой не больше $$$k$$$. После своего $$$i$$$-го хода игрок должен оказаться в $$$i$$$-м отрезке, то есть в такой координате $$$x$$$, что $$$l_i \le x \le r_i$$$. То есть:

  • После первого хода он должен оказаться внутри первого отрезка (от $$$l_1$$$ до $$$r_1$$$);
  • После второго хода он должен оказаться внутри второго отрезка (от $$$l_2$$$ до $$$r_2$$$);
  • ...
  • После $$$n$$$-го хода он должен оказаться внутри $$$n$$$-го отрезка (от $$$l_n$$$ до $$$r_n$$$).

Уровень считается пройденным, если игрок добрался до $$$n$$$-го отрезка, следуя правилам, описанным выше. Немного подумав, Поликарп понял, что при некоторых $$$k$$$ пройти уровень невозможно.

Поликарп не хочет, чтобы уровень был слишком простым, поэтому просит вас определить минимальное целое число $$$k$$$, при котором его возможно пройти.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество отрезков на уровне.

Далее следуют $$$n$$$ строк, $$$i$$$-я из которых содержит два числа $$$l_i$$$ и $$$r_i$$$ ($$$0 \le l_i \le r_i \le 10^9$$$) — границы $$$i$$$-го отрезка. Отрезки могут пересекаться.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите единственное целое число — минимальное целое $$$k$$$, при котором возможно пройти уровень.

Пример
Входные данные
4
5
1 5
3 4
5 6
8 10
0 1
3
0 2
0 1
0 3
3
3 8
10 18
6 11
4
10 20
0 5
15 17
2 2
Выходные данные
7
0
5
13
Примечание

В третьем примере игрок может сделать следующие ходы:

  • Переместиться из точки $$$0$$$ в точку $$$5$$$ ($$$3 \le 5 \le 8$$$);
  • Переместиться из точки $$$5$$$ в точку $$$10$$$ ($$$10 \le 10 \le 18$$$);
  • Переместиться из точки $$$10$$$ в точку $$$7$$$ ($$$6 \le 7 \le 11$$$).

Обратите внимание, что последним ходом игрок мог не перемещаться и всё равно пройти уровень.