本题的两个版本之间的唯一区别在于对 $k$ 的限制、时间限制和空间限制。只有当两个版本都被解决时，你才能进行 Hack。

Doremy 居住在一个由 $n$ 个城市组成的雨水充沛的国家，城市编号为 $1$ 到 $n$。

天气预报预测了未来 $m$ 天的降雨分布。在第 $i$ 天，区间 $[l_i, r_i]$ 内的城市将会下雨。如果一个城市在未来 $m$ 天内从未下过雨，则称该城市是干燥的。

事实证明，Doremy 拥有一种特殊的能力。她可以选择 $k$ 天，在这些天里将不会下雨。Doremy 想要计算在使用特殊能力后，干燥城市的最大数量。

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 10^4$) — 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$ ($1 \le n \le 2 \cdot 10^5$, $2 \le m \le 2 \cdot 10^5$, $2 \le k \le \min(10, m)$) — 城市的数量、天数以及 Doremy 可以阻止降雨的天数。

接下来有 $m$ 行。第 $i$ 行包含两个整数 $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — 第 $i$ 天的降雨覆盖范围。

保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $2 \cdot 10^5$。

输出格式

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

样例

输入样例 1

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

1
2
6
0
1000
17

说明

在第一个测试用例中，如果 Doremy 阻止：

• 第 1, 2 天的降雨，那么城市 2 将是干燥的；
• 第 2, 3 天的降雨，那么没有城市会是干燥的；
• 第 1, 3 天的降雨，那么没有城市会是干燥的。

因此，最多有 1 个干燥城市。

在第二个测试用例中，如果 Doremy 阻止：

• 第 1, 2 天的降雨，那么城市 1, 2 将是干燥的；
• 第 2, 3 天的降雨，那么城市 4, 5 将是干燥的；
• 第 1, 3 天的降雨，那么城市 1, 5 将是干燥的。

因此，最多有 2 个干燥城市。

在第三个测试用例中，最优方案是阻止第 1, 2, 4, 5 天的降雨。

在第四个测试用例中，总会有一天降雨覆盖所有城市，且无法被阻止。