如今,所有的小工具都是智能的:智能手机、智能音箱、智能灯泡,甚至智能电梯。机器升起。
人类抵抗组织的总部位于一座摩天大楼内。然而,智能电梯试图在不暴露自身的情况下减慢人们的速度。
摩天大楼里有$$$n$$$人在不同楼层等待电梯。每个人都想到达另一层楼。每个人的目的地楼层都不同于其他目的地楼层以及所有起始楼层。一开始,电梯位于一楼。它每单位时间移动一层楼。每当门打开时,它就会选择下一层并直接前往该楼层。电梯既可以到尚未乘电梯的人的起始楼层载人,也可以到已乘电梯的人的目的楼层载人下车。请注意,即使对于已经在电梯内的人来说,电梯也不会停在中间楼层。乘客登机和下机的时间可以忽略不计。电梯足够大,可以同时容纳所有人。
电梯的目标是最大化所有乘客被运送到目的地楼层的总时间。求从一楼开始到最后一位乘客下机的最大总时间。电梯无需返回一楼。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10\,000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ 表示人数 ($$$1 \le n \le 10^5$$$)。
以下 $$$n$$$ 行中的每一行都包含两个整数 $$$s_i$$$ 和 $$$f_i$$$ ($$$2 \le s_i, f_i \le 10^9$$$) 分别表示该人 $$$i$$$ 的起始楼层和目标楼层。输入中的所有 $$$2n$$$ 楼层都是成对不同的。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印运送所有人所需的最长时间。
示例
输入复制
315 322 78 4210 86 3
输出复制
62121
注意
第一个测试用例中,只有一个人。访问楼层的顺序为$$$1 \to 5 \to 3$$$,时间为$$$6$$$。
在第二个测试用例中,正确的序列之一是 $$$1 \to 8 \to 2 \to 7 \to 4$$$ ,时间为 $$$21$$$。
在第三个测试用例中,正确的序列之一是 $$$1 \to 10 \to 6 \to 3 \to 8$$$ ,时间为 $$$21$$$。