你的数学老师给了你以下问题:
$$$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]$$$ 作为答案。它是与所有给定线段至少具有一个公共点的最短线段。