CF1801B.Buying gifts

Little Sasha has two friends, whom he wants to please with gifts on the Eighth of March. To do this, he went to the largest shopping center in the city.

There are $n$ departments in the mall, each of which has exactly two stores. For convenience, we number the departments with integers from $1$ to $n$. It is known that gifts in the first store of the $i$ department cost $a_i$ rubles, and in the second store of the $i$ department — $b_i$ rubles.

Entering the mall, Sasha will visit each of the $n$ departments of the mall, and in each department, he will enter exactly one store. When Sasha gets into the $i$-th department, he will perform exactly one of two actions:

1. Buy a gift for the first friend, spending $a_i$ rubles on it.
2. Buy a gift for the second friend, spending $b_i$ rubles on it.

Sasha is going to buy at least one gift for each friend. Moreover, he wants to pick up gifts in such a way that the price difference of the most expensive gifts bought for friends is as small as possible so that no one is offended.

More formally: let $m_1$ be the maximum price of a gift bought to the first friend, and $m_2$ be the maximum price of a gift bought to the second friend. Sasha wants to choose gifts in such a way as to minimize the value of $\lvert m_1 - m_2 \rvert$.

小 Sasha 有两个朋友，他想在三月八日这天送他们礼物以表心意。为此，他来到了城里最大的购物中心。

商场里共有 $n$ 个部门，每个部门恰好有两家商店。为方便起见，我们将这些部门编号为 $1$ 至 $n$ 的整数。已知第 $i$ 个部门中，第一家商店的礼物价格为 $a_i$ 卢布，第二家商店的礼物价格为 $b_i$ 卢布。

Sasha 进入商场后，将依次访问全部 $n$ 个部门，且在每个部门中，他只会进入其中一家商店。当他到达第 $i$ 个部门时，他将严格执行以下两种操作之一：

1. 为第一位朋友购买一件礼物，花费 $a_i$ 卢布；
2. 为第二位朋友购买一件礼物，花费 $b_i$ 卢布。

Sasha 必须至少为每位朋友各买一件礼物。此外，他希望挑选礼物的方式使得两位朋友所收到的最贵礼物的价格之差尽可能小，从而避免任何一位朋友感到不快。

更形式化地说：设 $m_1$ 为送给第一位朋友的所有礼物中的最高价格，$m_2$ 为送给第二位朋友的所有礼物中的最高价格。Sasha 希望以某种方式选择礼物，使得 $\lvert m_1 - m_2 \rvert$ 的值最小。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1\,000$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 500\,000$) — the number of departments in the mall.

Each of the following $n$ lines of each test case contains two integers $a_i$ and $b_i$ ($0 \le a_i, b_i \le 10^9$) — the prices of gifts in the first and second store of the $i$ department, respectively.

It is guaranteed that the sum of $n$ over all test cases does not exceed $500\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

Print one integer — the minimum price difference of the most expensive gifts bought to friends.

输出一个整数——为朋友们购买的最贵礼物之间的最小价格差。

In the first test case, Sasha has two possible options: buy a gift for the first friend in the first department, and the second friend — in the second department, or vice versa. In the first case, $m_1 = m_2 = 1$, and in the second case — $m_1 = m_2 = 2$. In both cases, the answer is $0$. In the second test case, you can buy gifts for the first friend in the $2$, $4$ and $5$ departments, and for the second friend — in the $1$ and $3$ departments.So $m_1 = \max(2, 4, 2) = 4$, $m_2 = \max(5, 3) = 5$. The answer is $\lvert 4 - 5 \rvert = 1$.

在第一个测试用例中，Sasha 有两种可能的选择：为第一位朋友在第一个商场购买礼物，为第二位朋友在第二个商场购买礼物；或者反过来。在第一种情况下，$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$。