Jumping Through Segments
Contest: Codeforces Round 913 (Div. 3)
Difficulty rating: 1400
Tags: binary search, constructive algorithms

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.

Input format:
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$$$.

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

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
7
0
5
13

Editorial:
First, let's note that if we can pass a level with some value of $$$k$$$, then we can make all the same moves and pass it with a larger value. This allows us to use binary search for the answer.
To check whether it is possible to pass the level with a certain $$$k$$$, we will maintain a segment in which we can find ourselves. After each move, it expands by $$$k$$$ in both directions and is reduced to the intersection with the segment where the player must be at that move. If at any point the intersection becomes empty, then it is impossible to pass the level with such $$$k$$$.