SPIDEY1 - Mysterio s Menace

 

The nefarious Mysterio an expertise in illusions has a mind-warping hold on the City of New York, and it's up to Spidey to stop him before he takes over the entire city! Mysterio uses tiny cubes to create holograms which makes up his illusions. Mysterio has disguised the whole New York City into his own dream world. Mysterio now has created this illusive world with hologram cubes on a linear arena. To break this illusion Spiderman has to pick up as many cubes as he can from the arena. But wait thats not so easy!! Mysterio has disguised the arena too!!
The arena consists of rectangular rocks (of zero width) whose starting and ending x-coordinates are given.(The y-coordinates of the rocks is immaterial). For example consider the configuration of the rocks as follows: 2-4 ,3-8 ,4-8 ,8-9 ,9-10 here the first rock spans between x coordinate 2 to 4 and so on. Now if Spidey steps on a rock all other rocks which have overlapping segments with it disappear ie.,if he steps on rock 1  then rock 2 disappears as there is an overlapping segment namely the segment 3-4 but when he steps on rock 8-9 no other rock disappears as this rock has no overlapping segment with any other rock.Assume that Spidey can jump from any rock to any other rock and if he lands on a rock he destroys the hologram cube present on the rock. Poor Peter Parker is out of mind in this menace! Help him find the maximum number of cubes he can destroy.
Input Format
The first line of the input consists of a single integer T(1<=T<=100) specifying the number of test cases to follow .The first line of each test case is a single integer N(2<=N<=100000) the number of rocks in the arena. The next N lines of each test case consist of two space separated integers X1 X2 specifying the starting X-coordinate and the ending X-coordinate of rocks. The i+1 th line of each test case specifies the configuration of the i th rock.
0 <= X1 ,X2 <= 1000000000
Output Format
For each test case output a single integer M the maximum number of cubes that Spiderman can destroy.
SAMPLE INPUT:
2
5
2 4
3 8
4 8
8 9
9 10 
7
26 29
23 27
25 28
30 32
32 37
27 31
31 35
SAMPLE OUTPUT:
4
3 The nefarious Mysterio an expertise in illusions has a mind-warping hold on the City of New York, and it's up to Spidey to stop him before he takes over the entire city! Mysterio uses tiny cubes to create holograms which makes up his illusions. Mysterio has disguised the whole New York City into his own dream world. Mysterio now has created this illusive world with hologram cubes on a linear arena. To break this illusion Spiderman has to pick up as many cubes as he can from the arena. But wait thats not so easy!! Mysterio has disguised the arena too!!

The nefarious Mysterio an expertise in illusions has a mind-warping hold on the City of New York, and it's up to Spidey to stop him before he takes over the entire city! Mysterio uses tiny cubes to create holograms which makes up his illusions. Mysterio has disguised the whole New York City into his own dream world. Mysterio now has created this illusive world with hologram cubes on a linear arena. To break this illusion Spiderman has to destroy as many cubes as he can from the arena. But wait thats not so easy!! Mysterio has disguised the arena too!!

The arena consists of rectangular rocks (of zero width) whose starting and ending x-coordinates are given.(The y-coordinates of the rocks is immaterial). For example consider the configuration of the rocks as follows: 2-4 ,3-8 ,4-8 ,8-9 ,9-10 here the first rock spans between x coordinate 2 to 4 and so on. Now if Spidey steps on a rock all other rocks which have overlapping segments with it disappear ie.,if he steps on rock 1  then rock 2 disappears as there is an overlapping segment namely the segment 3-4 but when he steps on rock 8-9 no other rock disappears as this rock has no overlapping segment with any other rock.Assume that Spidey can jump from any rock to any other rock and if he lands on a rock he destroys the hologram cube present on the rock. Poor Peter Parker is out of mind in this menace! Help him find the maximum number of cubes he can destroy.

 

Input Format

The first line of the input consists of a single integer T(1<=T<=100) specifying the number of test cases to follow .The first line of each test case is a single integer N(2<=N<=100000) the number of rocks in the arena. The next N lines of each test case consist of two space separated integers X1 X2 specifying the starting X-coordinate and the ending X-coordinate of rocks. The i+1 th line of each test case specifies the configuration of the i th rock.

0 <= X1 ,X2 <= 1000000000

 

Output Format

For each test case output a single integer M the maximum number of cubes that Spiderman can destroy.

 

SAMPLE INPUT:

2
5
2 4
3 8
4 8
8 9
9 10
7
26 29
23 27
25 28
30 32
32 37
27 31
31 35

 

SAMPLE OUTPUT:

4
3

 

 


Added by:Rajeev
Date:2009-07-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST WHITESPACE

hide comments
2009-07-02 05:24:56 [Trichromatic] XilinX
See problem QUEST5. Almost the same.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.