310238: CF1802D. Buying gifts

D. Buying giftstime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output 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$.

Input

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$.

Output

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

Example

Input

2
2
1 2
2 1
5
1 5
2 7
3 3
4 10
2 5

Output

0
1

Note

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$.

题目大意：
小萨沙想给两个朋友在3月8日买礼物，为此他去了城里最大的购物中心。购物中心有n个部门，每个部门有两个商店，分别编号为1到n。已知第i部门第一个商店的礼物价格为a_i卢布，第二个商店的价格为b_i卢布。萨沙会进入每个部门的其中一个商店购买礼物，要么为第一个朋友花费a_i卢布，要么为第二个朋友花费b_i卢布。萨沙想为每位朋友至少买一个礼物，并且希望两位朋友收到的最贵礼物价格差尽可能小。形式上，设m_1为给第一个朋友买的礼物中的最高价格，m_2为给第二个朋友买的礼物中的最高价格，萨沙想最小化|m_1 - m_2|的值。

输入数据格式：
输入包含多个测试用例。第一行包含测试用例数t（1 ≤ t ≤ 1,000）。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（2 ≤ n ≤ 500,000）——购物中心的部门数。
接下来n行，每行包含两个整数a_i和b_i（0 ≤ a_i, b_i ≤ 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，答案为0。在第二个测试用例中，萨沙可以在第2、4、5部门给第一个朋友买礼物，在第1、3部门给第二个朋友买。所以m_1 = max(2, 4, 2) = 4，m_2 = max(5, 3) = 5。答案为|4 - 5| = 1。题目大意： 小萨沙想给两个朋友在3月8日买礼物，为此他去了城里最大的购物中心。购物中心有n个部门，每个部门有两个商店，分别编号为1到n。已知第i部门第一个商店的礼物价格为a_i卢布，第二个商店的价格为b_i卢布。萨沙会进入每个部门的其中一个商店购买礼物，要么为第一个朋友花费a_i卢布，要么为第二个朋友花费b_i卢布。萨沙想为每位朋友至少买一个礼物，并且希望两位朋友收到的最贵礼物价格差尽可能小。形式上，设m_1为给第一个朋友买的礼物中的最高价格，m_2为给第二个朋友买的礼物中的最高价格，萨沙想最小化|m_1 - m_2|的值。 输入数据格式： 输入包含多个测试用例。第一行包含测试用例数t（1 ≤ t ≤ 1,000）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（2 ≤ n ≤ 500,000）——购物中心的部门数。 接下来n行，每行包含两个整数a_i和b_i（0 ≤ a_i, b_i ≤ 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，答案为0。在第二个测试用例中，萨沙可以在第2、4、5部门给第一个朋友买礼物，在第1、3部门给第二个朋友买。所以m_1 = max(2, 4, 2) = 4，m_2 = max(5, 3) = 5。答案为|4 - 5| = 1。