Jumping Through Segments

题目描述

波利卡普正在为一款游戏设计一个关卡。关卡由数线上的 $n$ 段组成，其中 $i$ -th 段从坐标为 $l_i$ 的点开始，到坐标为 $r_i$ 的点结束。

玩家从坐标为 $0$ 的点开始通关。在一次移动中，他们可以移动到距离不超过 $k$ 的任意一点。在完成 $i$ 次移动后，玩家必须在 $i$ 段内着陆，也就是在坐标为 $x$ 的地方着陆，这样 $l_i \le x \le r_i$ 。这意味着

• 第一次移动后，他们必须在第一段（从 $l_1$ 到 $r_1$ ）内；
• 第二次移动后，它们必须位于第二个线段内（从 $l_2$ 到 $r_2$ ）；
• ...
• 第 $n$ 步之后，它们必须位于第 $n$ 段之内（从 $l_n$ 到 $r_n$ ）。

如果棋手按照上述规则下到了 $n$ 这一段，那么这关就算完成了。经过一番思考后，波利卡普意识到，在 $k$ 的某些值下是不可能完成这个关卡的。

波利卡普不希望这个关卡太简单，所以他要求你确定可以完成这个关卡的最小整数 $k$ 。

输入格式

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ )--测试用例的数量。下面是测试用例的说明。

每个测试用例的第一行包含一个整数 $n$ ( $1 \le n \le 2 \cdot 10^5$ )--关卡中的线段数。

接下来的 $n$ 行。

第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ （ $0 \le l_i \le r_i \le 10^9$ ）--第 $i$ 段的边界。线段可能相交。

保证所有测试案例中的 $n$ 之和不超过 $2 \cdot 10^5$ 。

输出格式

对于每个测试用例，输出一个整数--可以完成关卡的 $k$ 的最小值。

样例 #1

样例输入 #1

4
5
1 5
3 4
5 6
8 10
0 1
3
0 2
0 1
0 3
3
3 8
10 18
6 11
4
10 20
0 5
15 17
2 2

样例输出 #1

7
0
5
13

提示

在第三个例子中，棋手可以做出以下棋步：

• 从点 $0$ 移动到点 $5$ （ $3 \le 5 \le 8$ ）；
• 从点 $5$ 移至点 $10$ （ $10 \le 10 \le 18$ ）；
• 从点 $10$ 移动到点 $7$ （ $6 \le 7 \le 11$ ）。

请注意，在最后一步棋中，棋手可以选择不移动，但仍然可以完成这一关卡。