A. Математическая задача
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ваш учитель по математике задал вам следующую задачку:

Есть $$$n$$$ отрезков на оси (прямой) $$$x$$$, $$$[l_1; r_1], [l_2; r_2], \ldots, [l_n; r_n]$$$. Отрезок $$$[l; r]$$$ включает свои границы, то есть это множество таких $$$x$$$, что $$$l \le x \le r$$$. Длина отрезка $$$[l; r]$$$ равна $$$r - l$$$.

Два отрезка $$$[a; b]$$$ и $$$[c; d]$$$ имеют общую точку (пересекаются), если найдется такое $$$x$$$, что $$$a \leq x \leq b$$$ и $$$c \leq x \leq d$$$. Например, отрезки $$$[2; 5]$$$ и $$$[3; 10]$$$ имеют общую точку, но отрезки $$$[5; 6]$$$ и $$$[1; 4]$$$ — не имеют.

Вам требуется добавить один отрезок, который имеет хотя бы одну общую точку с каждым данным отрезком, и имеет как можно меньшую длину. Искомый отрезок может вырождаться в точку (то есть быть отрезком длины ноль). Искомый отрезок может как быть, так и не быть среди заданных $$$n$$$ отрезков.

Другими словами, вам нужно найти такой отрезок $$$[a; b]$$$, что $$$[a; b]$$$ и $$$[l_i; r_i]$$$ имеют общую точку для всех $$$i$$$, и при этом значение $$$b-a$$$ минимально.

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

В первой строке входных данных записано целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных в тесте. Далее следуют описания $$$t$$$ наборов входных данных.

В первой строке набора входных данных содержится одно целое число $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — количество отрезков. Следующие $$$n$$$ строк содержат описания отрезков — $$$i$$$-я из них содержит два целых числа $$$l_i,r_i$$$ ($$$1 \le l_i \le r_i \le 10^{9}$$$).

Сумма всех значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$10^5$$$.

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

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

Пример
Входные данные
4
3
4 5
5 9
7 7
5
11 19
4 17
16 16
3 12
14 17
1
1 10
1
1 1
Выходные данные
2
4
0
0
Примечание

В первом примере, можно взять отрезок $$$[5;7]$$$ как ответ. Это самый короткий отрезок, который имеет хотя бы одну общую точку со всеми данными.