write a go solution for Description:
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, and during these days it will not rain. Doremy wants to calculate the maximum number of dry cities after using the special power.

Input Format:
The input consists of multiple test cases. The first line contains a single integer t (1<=t<=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<=n<=2*10^5, 2<=m<=2*10^5, 2<=k<=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<=l_i<=r_i<=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*10^5.

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

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.. Output only the code with no comments, explanation, or additional text.