Description

deepl翻译

这个问题的两个版本之间的唯一区别在于 $k$ 的限制、时间限制和内存限制。只有所有版本的问题都解决了，你才能进行破解。

多瑞米生活在一个多雨的国家，由 $n$ 个城市组成，编号从 $1$ 到 $n$ 。

天气预报预测了未来 $m$ 天的雨量分布。在第 $i$ 天， $[l_i, r_i]$ 区间内的城市将下雨。如果一个城市在接下来的 $m$ 天里不会下雨，那么这个城市就被称为 "干旱"。

原来，多莱米有一种特殊的能力。她可以选择 $k$ 天，在这些天里不会下雨。多莱米想计算出使用特殊能力后，最多有多少个城市干旱。

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$, $2 \le k \le \min(10, m)$) — 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.

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

1
2
6
0
1000
17

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 $1,2,4,5$.

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