← 返回题目列表

Codeforces · 1227/A

A. 数学问题

中文机器翻译题面 查看原题

你的数学老师给了你以下问题:

$$$x$$$ 轴上有 $$$n$$$ 段,$$$[l_1; r_1],[l_2; r_2],\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$$$。

输出

对于每个测试用例,输出一个整数 - 与所有给定线段至少有一个公共点的线段的最小可能长度。

示例

输入 #1

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

输出 #1

2
4
0
0

注意

在示例的第一个测试用例中,我们可以选择段 $$$[5;7]$$$ 作为答案。它是与所有给定线段至少具有一个公共点的最短线段。