数组 $$$a_1, a_2, \ldots, a_m$$$ 最初用零填充。您将获得 $$$n$$$ 成对不同的段 $$$1 \le l_i \le r_i \le m$$$。您必须选择这些段的任意子集(特别是,您可以选择一个空集)。接下来,您执行以下操作:
- 对于每个 $$$i = 1, 2, \ldots, n$$$,如果段 $$$(l_i, r_i)$$$ 已被选择为子集,则对于每个索引 $$$l_i \le j \le r_i$$$,您将 $$$a_j$$$ 增加 $$$1$$$ (即 $$$a_j$$$ 被替换通过$$$a_j + 1$$$)。如果未选择段 $$$(l_i, r_i)$$$,则数组不会更改。
- 接下来(处理完 $$$i = 1, 2, \ldots, n$$$ 的所有值后),计算 $$$\max(a)$$$ 作为 $$$a$$$ 的所有元素中的最大值。类似地,计算 $$$\min(a)$$$ 作为最小值。
- 最后,所选段子集的成本声明为 $$$\max(a) - \min(a)$$$。
请找出所有段子集的最大成本。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 10^9$$$) - 段数和数组长度。
每个测试用例的以下 $$$n$$$ 行描述了这些段。这些行的第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$)。保证片段是两两不同的。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出给定段集的所有子集之间的最大成本。
示例
输入 #1
6 1 3 2 2 3 8 2 4 3 5 4 6 6 3 1 1 1 2 1 3 2 2 2 3 3 3 7 6 2 2 1 6 1 2 5 6 1 5 4 4 3 6 6 27 6 26 5 17 2 3 20 21 1 22 12 24 4 1000000000 2 999999999 3 1000000000 123456789 987654321 9274 123456789
输出 #1
1 3 2 3 4 4
注意
在第一个测试用例中,只有一个段可用。如果我们不选择它,则数组将为 $$$a = [0, 0, 0]$$$,并且此类(空)段子集的成本将为 $$$0$$$。但是,如果我们选择唯一的段,则数组将为 $$$a = [0, 1, 0]$$$,成本将为 $$$1 - 0 = 1$$$。
在第二个测试用例中,我们可以选择所有段:在这种情况下,数组将为 $$$a = [0, 1, 2, 3, 2, 1, 0, 0]$$$。成本将为 $$$3 - 0 = 3$$$。