310797: CF1889C1. Doremy's Drying Plan (Easy Version)

C1. Doremy's Drying Plan (Easy Version)time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The only differences between the two versions of this problem are the constraint on $k$, the time limit and the memory limit. You can make hacks only if all versions of the problem are solved.

Doremy lives in a rainy country consisting of $n$ cities numbered from $1$ to $n$.

The weather broadcast predicted the distribution of rain in the next $m$ days. In the $i$-th day, it will rain in the cities in the interval $[l_i, r_i]$. A city is called dry if it will never rain in that city in the next $m$ days.

It turns out that Doremy has a special power. She can choose $k$ days (in the easy version, $k = 2$), and during these days it will not rain. Doremy wants to calculate the maximum number of dry cities after using the special power.

Input

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line contains three integers $n$, $m$ and $k$ ($1\le n\le 2\cdot 10^5$, $2 \le m \le 2\cdot 10^5$, $k = 2$) — the number of cities, the number of days, and the number of days of rain that Doremy can prevent.

Then, $m$ lines follow. The $i$-th line contains two integers $l_i$, $r_i$ ($1\le l_i\le r_i\le n$) — the rain coverage on day $i$.

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $2\cdot 10^5$.

Output

For each test case, output one integer — the maximum number of dry cities.

ExampleInput

6
2 3 2
1 2
1 2
1 1
5 3 2
1 3
2 4
3 5
10 6 2
1 5
6 10
2 2
3 7
5 8
1 4
100 6 2
1 100
1 100
1 100
1 100
1 100
1 100
1000 2 2
1 1
1 1
20 5 2
9 20
3 3
10 11
11 13
6 18

Output

1
2
3
0
1000
15

Note

In the first test case, if Doremy prevents

• rain $1,2$, then city $2$ will be dry;
• rain $2,3$, then no city will be dry;
• rain $1,3$, then no city will be dry;

So there is at most $1$ dry city.

In the second test case, if Doremy prevents

• rain $1,2$, then city $1,2$ will be dry;
• rain $2,3$, then city $4,5$ will be dry;
• rain $1,3$, then city $1,5$ will be dry.

So there are at most $2$ dry cities.

In the third test case, it is optimal to prevent rain $2,5$.

In the forth test case, there is always $4$ days of rain that wets all the cities and cannot be prevented.

题目大意：
多雷米（Doremy）居住在一个由n个城市组成的多雨国家，这些城市从1到n编号。天气预报预测了接下来m天的降雨分布。在第i天，区间[l_i, r_i]内的城市将会下雨。如果一个城市在接下来的m天内永远不会下雨，则称为干燥城市。多雷米有一个特殊能力，她可以选择k天（在简单版本中，k = 2），在这些天里将不会下雨。多雷米想要计算使用特殊能力后，干燥城市的最大数量。

输入数据格式：
输入包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含三个整数n、m和k（1≤n≤2×10^5，2≤m≤2×10^5，k = 2）——城市的数量、天数和Doremy可以阻止的雨天数量。
然后是m行，每行包含两个整数l_i、r_i（1≤l_i≤r_i≤n）——第i天的降雨覆盖范围。
保证所有测试用例的n和m的总和不超过2×10^5。

输出数据格式：
对于每个测试用例，输出一个整数——干燥城市的最大数量。

示例：
输入：
6
2 3 2
1 2
1 2
1 1
5 3 2
1 3
2 4
3 5
10 6 2
1 5
6 10
2 2
3 7
5 8
1 4
100 6 2
1 100
1 100
1 100
1 100
1 100
1 100
1000 2 2
1 1
1 1
20 5 2
9 20
3 3
10 11
11 13
6 18

输出：
1
2
3
0
1000
15

注意：
在第一个测试用例中，如果Doremy阻止1,2天的雨，那么城市2将变得干燥；如果阻止2,3天的雨，那么没有城市会干燥；如果阻止1,3天的雨，那么没有城市会干燥。所以最多有1个干燥城市。
在第二个测试用例中，如果Doremy阻止1,2天的雨，那么城市1,2将变得干燥；如果阻止2,3天的雨，那么城市4,5将变得干燥；如果阻止1,3天的雨，那么城市1,5将变得干燥。所以最多有2个干燥城市。
在第三个测试用例中，最优的做法是阻止2,5天的雨。
在第四个测试用例中，总有4天的雨会淋湿所有城市，且无法阻止。题目大意： 多雷米（Doremy）居住在一个由n个城市组成的多雨国家，这些城市从1到n编号。天气预报预测了接下来m天的降雨分布。在第i天，区间[l_i, r_i]内的城市将会下雨。如果一个城市在接下来的m天内永远不会下雨，则称为干燥城市。多雷米有一个特殊能力，她可以选择k天（在简单版本中，k = 2），在这些天里将不会下雨。多雷米想要计算使用特殊能力后，干燥城市的最大数量。 输入数据格式： 输入包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含三个整数n、m和k（1≤n≤2×10^5，2≤m≤2×10^5，k = 2）——城市的数量、天数和Doremy可以阻止的雨天数量。 然后是m行，每行包含两个整数l_i、r_i（1≤l_i≤r_i≤n）——第i天的降雨覆盖范围。 保证所有测试用例的n和m的总和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出一个整数——干燥城市的最大数量。 示例： 输入： 6 2 3 2 1 2 1 2 1 1 5 3 2 1 3 2 4 3 5 10 6 2 1 5 6 10 2 2 3 7 5 8 1 4 100 6 2 1 100 1 100 1 100 1 100 1 100 1 100 1000 2 2 1 1 1 1 20 5 2 9 20 3 3 10 11 11 13 6 18 输出： 1 2 3 0 1000 15 注意： 在第一个测试用例中，如果Doremy阻止1,2天的雨，那么城市2将变得干燥；如果阻止2,3天的雨，那么没有城市会干燥；如果阻止1,3天的雨，那么没有城市会干燥。所以最多有1个干燥城市。 在第二个测试用例中，如果Doremy阻止1,2天的雨，那么城市1,2将变得干燥；如果阻止2,3天的雨，那么城市4,5将变得干燥；如果阻止1,3天的雨，那么城市1,5将变得干燥。所以最多有2个干燥城市。 在第三个测试用例中，最优的做法是阻止2,5天的雨。 在第四个测试用例中，总有4天的雨会淋湿所有城市，且无法阻止。