POSTERS - Election Posters

A parliamentary election was being held in Byteland. Its enterprising and orderly citizens decided to limit the entire election campaign to a single dedicated wall, so as not to ruin the panorama with countless posters and billboards. Every politician was 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 two or more adjacent sections.

With time, some of the posters were covered (partially or completely) by those of other politicians. Knowing 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

The input begins with the integer t, the number of test cases. Then t test cases follow.

Each test case begins with a line containing integer n - the number of posters (1 <= n <= 40000). Then n lines follow, the i-th (1 <= i <= n) containing exactly two integers li ri, denoting the numbers of the leftmost and rightmost sections covered by the i-th poster (1 <= li < ri <= 107). The input order corresponds to the order of hanging posters.

Output

For each test case output a line containing one integerĀ - the number of posters with visible sections.

Example

Sample input:
1
5
1 4
2 6
8 10
3 4
7 10

Sample output:
4

An illustration of the sample input is given below.

The wall with posters


Added by:adrian
Date:2004-07-19
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:VI Polish Collegiate Team Programming Contest (AMPPZ), 2001

hide comments
2013-05-22 11:34:30 Haidar Abboud
Comment #1 : done using an O(N log N) algorithm. Can it be solved in O(N) ?
Comment #2 :

Hint : Use coordinate compression to avoid TLE.
2013-05-18 21:19:51 coding_express
more test cases please
2013-05-18 21:19:05 coding_express
please give some tricky test cases
2013-05-15 03:31:04 昌(尼莫)
i am constantly getting WA but i tried various test cases and it seems to be working fine . So , if there are any good cases please help me
2013-01-18 21:44:37 saket diwakar
nice one.....:)

Last edit: 2013-02-01 03:51:38
2012-11-20 04:36:17 Paul Draper
A good test case that I failed on at first
1
3
3 7
1 4
5 10

2
2010-11-15 02:33:46 Brian Bi
The judge is occasionally buggy in this way. If it bothers you that much, you can contact the problem setter and ask him to rejudge it...
2010-07-30 21:16:36 shivmitra mishra
there is an AC solution using 0.00 sec and 0k memory..hws that possible while other solutions have used memory like 2.0 M ????
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.