Help Ribo

saif_sust MU Practice Contest for J...
Limits 2s, 1.0 GB

Ribo is a famous robot, engineered by SUST robotics club. He can do
wonderful things like answering your questions in Bengali, recognizing people,
and detecting your mood based on how you stare at him. He has actually won
several competitions by showing his true intelligence.

However, he has recently become very busy and needs your help. Everyone
tries to get their work done by him, and he cannot disappoint any of them. Each
work i has to begin at time si and finish at time fi. Ribo has a magic switch integrated into him. He can finish one work at a time by pressing the switch.

The magical thing about the switch is that every work j will automatically be
finished, if, the switch is pressed for work i such that sj > si and fj < fi. Ribo
has got the list of the works and now he wonders what is the minimum number
of presses he has to make to get all the works done. Can you help him?

Input

The first line of the input contains an integer T (T ≤ 20), the number of test
cases to follow. Each test case begins with one integer N (N ≤ 100000), the
number of works for the case. Each of the following N lines contains two integers
si and fi (1 ≤ sifi ≤ 109).

Output

Produce a single of output for each case that will contain the case number
followed by the minimum number of presses Ribo has to make to get all the
works done. See the sample cases for the exact format.

Sample

InputOutput
3
3
1 7
2 5
4 11
3
2 9
5 9
10 12
2
1 4
2 3
Case 1: 2
Case 2: 3
Case 3: 1

Submit

Login to submit.

Statistics

68% Solution Ratio
fahim5466Earliest, Jul '17
Fake_DeathFastest, 101701.4s
avivillaLightest, 918 kB
fahim5466Shortest, 596B
Toph uses cookies. By continuing you agree to our Cookie Policy.