Time Limit: 3 second(s) | Memory Limit: 64 MB |
Election Day has arrived in Bangladesh. The citizens are aware of the fact that the candidates will poster the entire country, ruining the walls, pillars and windows. Thus they have decided to limit the entire election campaign to a single dedicated wall. Every candidate will be allowed to hang exactly one poster on the wall. All posters extend from top to bottom, but are hung at different points of the wall, and may be of different width. The wall is divided horizontally into sections, and a poster completely occupies one or more adjacent sections.
But the candidates used the wall without considering the posters from other candidates. Some of the posters were covered (partially or completely) by those of other candidates. Now you are given the location of all the posters and the order in which they were hung, determine how many posters have at least one visible section in the end.
Input starts with an integer T (≤ 8), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 10^{5}) denoting the number of posters. Each of the next n lines contains two integers l_{i} r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ 2*n) denoting the number of the wall section occupied by the left end and the right end of the i^{th} poster, respectively. The input order corresponds to the order of hanging posters.
For each case, print the case number and the number of posters with visible sections.
Sample Input |
Output for Sample Input |
1 5 1 4 2 6 8 10 3 4 7 10 |
Case 1: 4 |
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |