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\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 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.