CF1834D.Survey in Class

Zinaida Viktorovna has $n$ students in her history class. The homework for today included $m$ topics, but the students had little time to prepare, so $i$-th student learned only topics from $l_i$ to $r_i$ inclusive.

At the beginning of the lesson, each student holds their hand at $0$. The teacher wants to ask some topics. It goes like this:

• The teacher asks the topic $k$.
• If the student has learned topic $k$, then he raises his hand by $1$, otherwise he lower it by $1$.

Each topic Zinaida Viktorovna can ask no more than one time.

Find the maximum difference of the heights of the highest and the lowest hand that can be in class after the survey.

Note that the student's hand can go below $0$.

齐娜伊达·维克托罗夫娜的历史课上有 $n$ 名学生。今天的作业包含 $m$ 个主题，但学生们准备时间很少，因此第 $i$ 名学生仅学习了从主题 $l_i$ 到 $r_i$（含端点）的所有主题。

上课伊始，每名学生的手都处于高度 $0$。老师打算提问若干主题，过程如下：

• 老师提问主题 $k$；
• 若该学生学过主题 $k$，则其手的高度增加 $1$；否则其手的高度减少 $1$。

每个主题齐娜伊达·维克托罗夫娜至多提问一次。

求在全部提问结束后，全班中最高手高与最低手高之差的最大可能值。

注意：学生的手高可以低于 $0$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 10^5, 1 \le m \le 10^9$) — the number of students and the number of topics, respectively.

Each of the next $n$ lines of each test case contain two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le m$) — the endpoints of the segment of topics that $i$-th student has learned.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$ 个学生已学习的主题区间 $[l_i, r_i]$ 的端点。

保证所有测试用例的 $n$ 值之和不超过 $10^5$。

For each test case, print one integer — the maximum difference of the heights of the highest and the lowest hand that can be in the class after the survey.

对于每个测试用例，输出一个整数——即调查结束后，班级中最高与最矮学生身高之差的最大可能值。

In the first test case, Zinaida Viktorovna can ask the topics $5, 6, 7, 8$. Then the hand of the $2$-nd student will be at the height of $4$, and the hand of the $4$-th will be at the height of $-2$, that is, the difference will be equal to $6$.

In the second test case, you can ask about the topics $1$ and $3$. Then the hand of the $1$-st student will be at the height of $2$ and the hand of the $3$-rd student will be at the height of $-2$. So the difference will be $4$.

In the third test case, the difference between the highest and lowest hand will be $0$ for any set of topics asked.

In the fifth test case, you can ask all topics. Then the difference between the heights of the $1$-st and $3$-rd students' hands will be $12$.

在第一个测试用例中，季娜伊达·维克托罗夫娜可以提问主题 $5, 6, 7, 8$。此时第 $2$ 位学生的手位于高度 $4$，第 $4$ 位学生的手位于高度 $-2$，即二者之差为 $6$。

在第二个测试用例中，可以提问主题 $1$ 和 $3$。此时第 $1$ 位学生的手位于高度 $2$，第 $3$ 位学生的手位于高度 $-2$，因此二者之差为 $4$。

在第三个测试用例中，无论选择哪一组主题进行提问，最高与最低的手部高度之差均为 $0$。

在第五个测试用例中，可以提问所有主题。此时第 $1$ 位与第 $3$ 位学生手部高度之差为 $12$。