题目描述

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

在 $x$ 轴上有 $n$ 个段，$[l_1;r_1],[l_2;r_2]\ldots[l_n;r_n]$。段 $[l;r]$ 包括了边界，即它是 $x$ 的集合，其中 $l \leq x \leq 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]$ 有一个公共点，并且 $b-a$ 是最小的。

输入格式

第一行包含一个整数 $t(1 \leq t \leq 100)$，表示测试用例数量。然后是 $n$ 个测试用例。

没个测试用例的第一行包含一个整数 $n(1 \leq n \leq 10^5)$，表示段数。以下 $n$ 行描述每一段：其中第 $i$ 个包含两个整数 $l_i,r_i(1 \leq l_i \leq r_i \leq 10^9)$。

输入中的所有测试用例的每个 $n$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出一个整数，表示与所有给定段至少有一个公共点的段的最小长度。

说明/提示

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

样例

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

2
4
0
0