B. Покупка подарков
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
У маленького Саши есть две подруги, которых он хочет порадовать подарками на Восьмое марта. Для этого он отправился в самый большой торговый центр в городе.

В торговом центре есть $$$n$$$ отделов, в каждом из которых находятся ровно два магазина. Для удобства пронумеруем отделы целыми числами от $$$1$$$ до $$$n$$$. Известно, что подарки в первом магазине $$$i$$$-го отдела стоят $$$a_i$$$ рублей, а во втором магазине $$$i$$$-го отдела — $$$b_i$$$ рублей.

Войдя в торговый центр, Саша посетит каждый из $$$n$$$ отделов торгового центра, причем в каждом отделе он зайдет ровно в один магазин. Когда Саша попадет в $$$i$$$-й отдел, он выполнит ровно одно из двух действий:

  1. Купить подарок первой подруге, потратив на это $$$a_i$$$ рублей.
  2. Купить подарок второй подруге, потратив на это $$$b_i$$$ рублей.

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

Более формально: пусть $$$m_1$$$ — максимальная цена подарка, купленного первой подруге, а $$$m_2$$$ — максимальная цена подарка, купленного второй подруге. Саша хочет выбрать подарки таким образом, чтобы минимизировать величину $$$\lvert m_1 - m_2 \rvert$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 500\,000$$$) — количество отделов в торговом центре.

Каждая из следующих $$$n$$$ строк каждого набора входных данных содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$0 \le a_i, b_i \le 10^9$$$) — цены подарков в первом и втором магазине $$$i$$$-го отдела, соответственно.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$500\,000$$$.

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

Выведите одно целое число — минимальную разность цен самых дорогих подарков, купленных подругам.

Пример

Входные данные
2
2
1 2
2 1
5
1 5
2 7
3 3
4 10
2 5
Выходные данные
0
1
Примечание

В первом наборе входных данных у Саши есть два возможных варианта действий: купить подарок первой подруге в первом отделе, а второй подруге — во втором отделе, или наоборот. В первом случае $$$m_1 = m_2 = 1$$$, а во втором случае — $$$m_1 = m_2 = 2$$$. В обоих случаях ответ равен $$$0$$$. Во втором наборе входных данных можно купить подарки для первой подруги в $$$2$$$-м, $$$4$$$-м и $$$5$$$-м отделах, а для второй подруги — в $$$1$$$-м и $$$3$$$-м отделах. Таким образом, $$$m_1 = \max(2, 4, 2) = 4$$$, $$$m_2 = \max(5, 3) = 5$$$. Ответ равен $$$\lvert 4 - 5 \rvert = 1$$$.