计算机科学与技术系的年度迎新晚会即将到来！许多学生受邀参加晚会，每位学生都可以选择唱歌或表演相声。这让总导演非常头疼：如何安排表演，使得每位学生都能上台，且观众的满意度最大化？

为了解决这个问题，导演提出了一个模型。在这个模型中，每位学生有两个属性：唱歌能力和相声能力。唱歌带来的观众满意度值是所有选择唱歌的学生中唱歌能力的最大值。同样，相声带来的观众满意度值是所有选择相声的学生中相声能力的最大值。

奇怪的是，整个晚会的总满意度值与唱歌和相声满意度值之间的绝对差值负相关。问题是，两种表演的满意度值之间的最小可能绝对差值是多少？

注意： 每位学生必须恰好选择一种表演方式； 至少有一名学生唱歌，且至少有一名学生表演相声。

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 70$)，表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 100\,000$)，表示受邀参加晚会的学生人数。接下来 $n$ 行，每行包含两个整数 $x$ 和 $y$ ($0 \le x, y \le 10^{18}$)，分别表示一名学生的唱歌能力和相声能力。

保证所有测试用例的 $n$ 之和不超过 $1\,000\,000$。

输出格式

对于每个测试用例，输出一个整数：两种表演的满意度值之间可能的最小绝对差值。

样例

输入 1

2
5
27 46
89 13
55 8
71 86
22 35
3
3 5
4 7
6 2

输出 1

3
1