D. Assignment Allocation
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ assignments in a course, and $$$d$$$ days in the semester. Assignment $$$i$$$ is assigned at the start of day $$$S_i$$$ and is due by the end of day $$$E_i$$$. Thus, you can work on assignment $$$i$$$ on any day $$$t$$$ such that $$$S_i \leq t \leq E_i$$$.

The professor has a forgiveness policy, where she will drop at most $$$k$$$ missed assignments from the final grade.

You have recently been obsessed with Honkai Star Rail, and decide that you will only complete at most one assignment per day, to make time for your daily quests. As an optimally lazy student, what is the minimum number of missed assignments on your final grade?

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$d$$$, and $$$k$$$ ($$$1 \leq n,d \leq 2\cdot10^5$$$, $$$0 \leq k \leq n$$$) — the number of assignments, the number of days in the semester, and the maximum number of forgiven assignments, respectively.

Each of the following $$$n$$$ lines contains two integers $$$S_i$$$ and $$$E_i$$$ ($$$1 \leq S_i \leq E_i \leq d$$$) — the assignment start date and end date.

It is guaranteed that the sum of $$$n$$$ over all test cases is at most $$$2 \cdot 10^5$$$, and the sum of $$$d$$$ over all test cases is at most $$$2 \cdot 10^5$$$.

Output

For each test case, output the minimum number of points you will lose if you complete at most one assignment per day.

Example
Input
3
2 1 0
1 1
1 1
3 2 1
1 1
1 2
2 2
9 16 0
1 8
1 5
3 12
1 3
1 3
2 4
2 4
1 1
3 6
Output
1
0
1