商场中有$$$n$$$个部门,每个部门正好有两家商店。为了方便起见,我们用从 $$$1$$$ 到 $$$n$$$ 的整数对部门进行编号。据了解,$$$i$$$ 部门第一家商店的礼物价格为 $$$a_i$$$ 卢布,$$$i$$$ 部门第二家商店的礼物价格为 $$$b_i$$$ 卢布。
进入商场,Sasha将访问商场的每个$$$n$$$部门,并且在每个部门中,他将恰好进入一家商店。当 Sasha 进入第 $$$i$$$ 部门时,他将执行以下两个操作之一:
1. 为第一个朋友购买一份礼物,花费 $$$a_i$$$ 卢布。
2. 为第二个朋友购买一份礼物,花费 $$$b_i$$$ 卢布。
Sasha 将至少为每位朋友购买一件礼物。而且,他在挑选礼物时,希望给朋友买的最贵的礼物的价差尽可能小,以免得罪人。
更正式地说:令 $$$m_1$$$ 为购买给第一个朋友的礼物的最高价格,$$$m_2$$$ 为购买给第二个朋友的礼物的最高价格。 Sasha 希望以最小化 $$$\lvert m_1 - m_2 \rvert$$$ 的值的方式选择礼物。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1\,000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 500\,000$$$) — 商场中的部门数量。
每个测试用例的以下 $$$n$$$ 行均包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$0 \le a_i, b_i \le 10^9$$$) - 分别是 $$$i$$$ 部门第一家和第二家商店的礼物价格。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$500\,000$$$。
输出
打印一个整数——给朋友买的最贵礼物的最小价差。
示例
输入 #1
2 2 1 2 2 1 5 1 5 2 7 3 3 4 10 2 5
输出 #1
0 1
注意
在第一个测试用例中,Sasha 有两种可能的选择:为第一部门的第一个朋友和第二部门的第二个朋友购买礼物,反之亦然。在第一种情况下,$$$m_1 = m_2 = 1$$$,在第二种情况下 - $$$m_1 = m_2 = 2$$$。在这两种情况下,答案都是$$$0$$$。 在第二个测试用例中,您可以为 $$$2$$$、$$$4$$$ 和 $$$5$$$ 部门的第一个朋友购买礼物,也可以为 $$$1$$$ 和 $$$3$$$ 部门的第二个朋友购买礼物。因此 $$$m_1 = \max(2, 4, 2) = 4$$$、$$$m_2 = \max(5, 3) = 5$$$。答案是$$$\lvert 4 - 5 \rvert = 1$$$。