多雷米的烘干计划（简单版）

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

本题有简单版和困难版，两个版本仅在 $k$ 的限制、时间限制和内存限制上不同。本题为简单版，固定 $k=2$。

多雷米生活在一个多雨的国家，其中有 $n$ 座城市，编号为 $1$ 到 $n$。

天气预报给出了接下来 $m$ 天的降雨情况：第 $i$ 天，编号位于区间 $[l_i,r_i]$ 内的所有城市都会下雨。如果一座城市在这 $m$ 天中从未下雨，就称它为干燥城市。

多雷米可以选择恰好 $k=2$ 个不同的日子，使这两天完全不下雨。求使用能力后，最多可以有多少座干燥城市。

输入格式

输入包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数。

每组测试数据的第一行包含三个整数 $n,m,k$。本题保证 $k=2$。

接下来 $m$ 行，每行包含两个整数 $l_i,r_i$，表示第 $i$ 天的降雨城市区间。

输出格式

对于每组测试数据，输出一个整数，表示最多可以得到的干燥城市数量。

样例输入 1

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

1
2
3
0
1000
15

样例说明

在第一组测试数据中，阻止第 $1,2$ 天的降雨后，城市 $2$ 保持干燥，答案为 $1$。

在第二组测试数据中，阻止第 $1,2$ 天可使城市 $1,2$ 干燥；阻止第 $2,3$ 天可使城市 $4,5$ 干燥；阻止第 $1,3$ 天可使城市 $1,5$ 干燥，因此答案为 $2$。

第三组测试数据的一种最优方案是阻止第 $2,5$ 天。第四组测试数据中始终还有四天覆盖全部城市，所以答案为 $0$。

数据范围

对于所有测试数据：

• $1\le t\le 10^4$；
• $1\le n\le 2\times10^5$，$2\le m\le 2\times10^5$，$k=2$；
• $1\le l_i\le r_i\le n$；
• 所有测试数据中 $n$ 的总和不超过 $2\times10^5$，$m$ 的总和不超过 $2\times10^5$。