We are planning to design a new operating system. Like other OS we will use the techniques of processes, schedulers, locks, etc. The basic plan is to use the OS in hardwires that have low configurations. So, efficiency matters. That's why we want to minimize the cost as well as power consumption.
To be more specific, there are n processes, and each process starts its execution in timestamp si, and ends its execution in timestamp ti. For simplicity, assume that the timestamps are represented as integers. Now, when a process is being executed, we need a wrapper program to monitor that. If a process tries to harm the system or wants to take hold of some restricted resources or even tries to invoke some forbidden methods, the wrapper program will halt the process and generate appropriate error signals. But the problem is that a wrapper program cannot monitor more than one process at any given timestamp and also when it's been assigned to a process, it will have to wait until the process finishes. But once the process terminates, the same wrapper program can be used for monitoring other processes.
Given the process schedules, we want to find the minimum number of wrapper programs to monitor them according to the given restrictions.
Input
Input starts with an integer T (≤ 20), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 50000). Each of the next n lines contains two integers si ti (1 ≤ si ≤ ti ≤ 109).
Output
For each case, print the case number and the minimum number of wrapper programs to monitor all the processes.
Sample
| Sample Input | Sample Output |
|---|---|
2 2 1 3 3 5 4 1 10 10 20 11 21 3 5 | Case 1: 2 Case 2: 2 |
Notes
Dataset is huge, use faster I/O methods.