Status:  Past  Start:  20111201 14:00:00  End:  20111201 19:10:00 
The Caribbean Training Contest #29
Problem
1645  Painting Wall
Created by  Carlos Julio Figueiras Carrera 
Added by  ymondelo20 (20111129) 
Limits 
Total Time: 2000 MS
Memory: 62 MB  Output: 64 MB  Size:
29 KB

Enabled languages  
Available in 
Description
Andrea is a girl who just don't likes to play, but also enjoys painting, this time, his father told her to paint the new wall how she wants. Andrea has M cans of paint of different colors for painting the wall. The wall will be represented by an array of many positions. Andrea, for each color, select an interval [A,B] which be completely painted that color. She will do the same procedure for the M colors. After finishing her task his father asked how many differents colors can be seen in the wall after painting, but as the wall is too large makes it a very difficult job and she needs your help to answer the question.
Andrea is a girl who just don't likes to play, but also enjoys painting, this time, his father told her to paint the new wall how she wants. Andrea has M cans of paint of different colors for painting the wall. The wall will be represented by an array of many positions. Andrea, for each color, select an interval [A,B] which be completely painted that color. She will do the same procedure for the M colors. After finishing her task his father asked how many differents colors can be seen in the wall after painting, but as the wall is too large makes it a very difficult job and she needs your help to answer the question.
Andrea is a girl who just don't likes to play, but also enjoys painting, this time, his father told her to paint the new wall how she wants. Andrea has M cans of paint of different colors for painting the wall. The wall will be represented by an array of many positions. Andrea, for each color, select an interval [A,B] which be completely painted that color. She will do the same procedure for the M colors. After finishing her task his father asked how many differents colors can be seen in the wall after painting, but as the wall is too large makes it a very difficult job and she needs your help to answer the question.
Input specification
One integer T <= 20 (the number of test cases), and for each case:
Line 1: M <= 10^5
Line 2...M+1: 1 <= A,B <= 10^6
Consecutives test cases will be separated by empty line.
Line 1: M <= 10^5
Line 2...M+1: 1 <= A,B <= 10^6
Consecutives test cases will be separated by empty line.
One integer T <= 20 (the number of test cases), and for each case:
Line 1: M <= 10^5
Line 2...M+1: 1 <= A,B <= 10^6
Consecutives test cases will be separated by empty line.
Line 1: M <= 10^5
Line 2...M+1: 1 <= A,B <= 10^6
Consecutives test cases will be separated by empty line.
One integer T <= 20 (the number of test cases), and for each case:
Line 1: M <= 10^5
Line 2...M+1: 1 <= A,B <= 10^6
Consecutives test cases will be separated by empty line.
Line 1: M <= 10^5
Line 2...M+1: 1 <= A,B <= 10^6
Consecutives test cases will be separated by empty line.
Output specification
For each case, one and only one line with one integer, how many differents colors can be seen in the wall after paint.
For each case, one and only one line with one integer, how many differents colors can be seen in the wall after paint.
One integer T <= 20 (the number of test cases), and for each case:
Line 1: M <= 10^5
Line 2...M+1: 1 <= A,B <= 10^6
Consecutives test cases will be separated by empty line.
Line 1: M <= 10^5
Line 2...M+1: 1 <= A,B <= 10^6
Consecutives test cases will be separated by empty line.
Sample input
1
3
1 100
10 10
8 15
Sample output
2
Hint(s)
At the begin the wall has not paint.
At the begin the wall has not paint.
At the begin the wall has not paint.