A laptop, also called a notebook, is a personal computer for mobile use. A laptop integrates most of the typical components of a desktop computer, including a display, a keyboard, a CD-ROM drive, etc. Nevertheless, a distinct feature of a laptop is portability, which means that a laptop can be used in many places — not only at home and at the office, but also in coffee shops, in lecture halls and libraries, or at a meeting room, etc. Laptops are typically powered by an internal rechargeable battery that is charged using an external power supply. Typical battery life for standard laptops is two to five hours, but may drop to as little as one hour when doing energy-intensive tasks. A battery’s performance gradually decreases with time. To reduce energy consumption, a laptop has a transition to a standby or hibernate mode if it has been idle for a while. In this mode, no energy is consumed, but a fixed amount of energy, specifically, equal to the energy consumed during a unit time, is required when moving the laptop from the hibernate mode to the active mode. So, minimizing the overall energy consumption is equivalent to finding a schedule to minimize the number of idle periods. Each task Ti is given with a release time ri and a deadline di, where Ti is executed in a unit time, and it should be scheduled and completed within the time interval [ri,di]. Also you can assume the following conditions on the problem instance are satisfied: (1) ri and di are integers and the Ti tasks must be scheduled at integral times. (2) ri ≤rj ifandonlyifdi ≤dj. (3) There is at least one schedule in which all the tasks can be scheduled and completed within their time intervals. The goal is to minimize the number of idle periods such that all the tasks are scheduled. Note that the idle periods are assumed to occur after a task is first scheduled. For example, there are five tasks Ti with release times ri and deadlines di, i = 1, . . . , 5, satisfying that [r1,d1] = [4,8], [r2,d2] = [1,3], [r3,d3] = [8,10], [r4,d4] = [0,3] and [r5,d5] = [6,8]. Figure 1 shows a schedule in which the number of idle periods is 3. However, there is a schedule with only one idle period as shown in Figure 2. Figure 1. A schedule with 3 idle periods. Figure 2. A schedule with the minimum number of idle periods
2/2 Input Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. The first line of each test case contains an integer n (1 ≤ n ≤ 100, 000), the number of the given tasks. In the next n lines of each test case, the i-th line contains two integer numbers ri and di, representing the release time and the deadline of the task Ti, respectively, where 0 ≤ ri ≤ di ≤ 1, 000, 000. Output Your program is to write to standard output. Print exactly one line for each test case. The line contains the minimum number of idle periods. The following shows sample input and output for two test cases. Sample Input 2 5 48 13 8 10 03 68 9 04 04 36 36 57 68 8 11 9 11 10 11 Sample Output 1 0