1645 - Painting Wall

Created by Carlos Julio Figueiras Carrera
Added by ymondelo20 (2011-11-29)
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.
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.
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.

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.

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.