Zinaida Viktorovna 的历史课上有 $$$n$$$ 名学生。今天的作业包括$$$m$$$主题,但学生们准备的时间很少,所以$$$i$$$-th学生只学习了从$$$l_i$$$到$$$r_i$$$的主题。
课程开始时,每个学生都将手握在 $$$0$$$ 处。老师想问一些话题。事情是这样的:
- 老师提出主题$$$k$$$。
- 如果学生已经学习了主题$$$k$$$,那么他将举手$$$1$$$,否则他将手放下$$$1$$$。
每个主题 Zinaida Viktorovna 只能询问一次。
找出调查后班级中可以出现的最高手和最低手的高度的最大差值。
请注意,学生的手牌可能会低于 $$$0$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 10^5, 1 \le m \le 10^9$$$) – 分别是学生数量和主题数量。
每个测试用例接下来的 $$$n$$$ 行都包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$) - 第 $$$i$$$ 个学生已学习的主题段的端点。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印一个整数 - 调查后班级中最高手和最低手的高度的最大差值。
示例
输入 #1
6 4 8 2 6 4 8 2 7 1 5 3 3 1 3 2 3 2 2 3 5 1 5 1 5 1 5 3 5 1 1 3 3 5 5 4 7 1 7 1 3 3 3 4 5 2 4 1 3 2 4
输出 #1
6 4 0 2 12 2
注意
在第一个测试用例中,Zinaida Viktorovna 可以询问主题 $$$5, 6, 7, 8$$$。那么第 $$$2$$$-nd 学生的手将位于 $$$4$$$ 的高度,第 $$$4$$$-th 学生的手将位于 $$$-2$$$ 的高度,也就是说,差值将等于 $$$6$$$。
在第二个测试用例中,您可以询问主题 $$$1$$$ 和 $$$3$$$。那么第 $$$1$$$-st 学生的手将位于 $$$2$$$ 高度,$$$3$$$-rd 学生的手将位于 $$$-2$$$ 高度。所以差额为$$$4$$$。
在第三个测试用例中,对于所询问的任何一组主题,最高手牌和最低手牌之间的差异将为 $$$0$$$。
在第五个测试用例中,您可以询问所有主题。那么$$$1$$$-st 和$$$3$$$-rd 学生的手部高度之间的差异将为$$$12$$$。