Server Time: Wed Jun 19, 2019 5:39 pm
Welcome ( logout
1207 - Posters for Election
  PDF (English) Statistics Forum
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 ≤ 105) denoting the number of posters. Each of the next n lines contains two integers li ri (1 ≤ li ≤ ri ≤ 2*n) denoting the number of the wall section occupied by the left end and the right end of the ith 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 4

2 6

8 10

3 4

7 10

Case 1: 4


  1. Dataset is huge. Use faster I/O methods.
  2. Illustration for sample input:

Special Thanks: Jane Alam Jan (Description, Solution, Dataset)
Developed and Maintained by
Copyright © 2012
LightOJ, Jane Alam Jan