Polycarp 正在设计游戏的关卡。该级别由数轴上的 $$$n$$$ 段组成,其中第 $$$i$$$ 段从坐标 $$$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$$$ 段,则认为该关卡已完成。经过一番思考,Polycarp 意识到用 $$$k$$$ 的某些值来完成关卡是不可能的。
Polycarp 不希望关卡太简单,因此他要求你确定可以完成关卡的最小整数 $$$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
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$$$)。
请注意,对于最后一步,玩家可以选择不移动并仍然完成关卡。