CF1907D.Jumping Through Segments

Polycarp is designing a level for a game. The level consists of $n$ segments on the number line, where the $i$-th segment starts at the point with coordinate $l_i$ and ends at the point with coordinate $r_i$.

The player starts the level at the point with coordinate $0$. In one move, they can move to any point that is within a distance of no more than $k$. After their $i$-th move, the player must land within the $i$-th segment, that is, at a coordinate $x$ such that $l_i \le x \le r_i$. This means:

• After the first move, they must be inside the first segment (from $l_1$ to $r_1$);
• After the second move, they must be inside the second segment (from $l_2$ to $r_2$);
• ...
• After the $n$-th move, they must be inside the $n$-th segment (from $l_n$ to $r_n$).

The level is considered completed if the player reaches the $n$-th segment, following the rules described above. After some thought, Polycarp realized that it is impossible to complete the level with some values of $k$.

Polycarp does not want the level to be too easy, so he asks you to determine the minimum integer $k$ with which it is possible to complete the level.

Polycarp 正在为一款游戏设计一个关卡。该关卡由数轴上的 $n$ 个线段组成，其中第 $i$ 个线段起始于坐标 $l_i$，终止于坐标 $r_i$。

玩家从坐标为 $0$ 的点开始闯关。每次移动中，玩家最多可移动距离 $k$（即：移动后与移动前的坐标之差的绝对值不超过 $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$ 个线段，则该关卡视为完成。经过思考，Polycarp 意识到：对某些 $k$ 值，该关卡根本无法完成。

Polycarp 不希望关卡过于简单，因此他请你找出能够完成该关卡的最小整数 $k$。

The first line contains a single integer $t$ ($1 \le t \le 10^4$)—the number of test cases. Descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$)—the number of segments in the level.

The following $n$ lines.

The $i$-th line contain two integers $l_i$ and $r_i$ ($0 \le l_i \le r_i \le 10^9$)—the boundaries of the $i$-th segment. Segments may intersect.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, output a single integer—the minimum value of $k$ with which it is possible to complete the level.

对于每个测试用例，输出一个整数——能够完成该关卡的最小 $k$ 值。

In the third example, the player can make the following moves:

• Move from point $0$ to point $5$ ($3 \le 5 \le 8$);
• Move from point $5$ to point $10$ ($10 \le 10 \le 18$);
• Move from point $10$ to point $7$ ($6 \le 7 \le 11$).

Note that for the last move, the player could have chosen not to move and still complete the level.

在第三个例子中，玩家可以执行以下操作：

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

注意：对于最后一次移动，玩家本可以选择不移动，依然能完成关卡。