B'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 <= x <= r_i . This means: 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. The first line contains a single integer t ( 1 <= t <= 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 <= n <= 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 <= l_i <= r_i <= 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 . For each test case, output a single integer --the minimum value of k with which it is possible to complete the level. In the third example, the player can make the following moves: Note that for the last move, the player could have chosen not to move and still complete the level. '...