Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Help Ribo

By saif_sust · 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 &le; 20), the number of test cases to follow. Each test case begins with one integer N (N &le; 100000), the number of works for the case. Each of the following N lines contains two integers si and fi (1 &le; si &le; fi &le; 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

    Discussion

    Statistics


    68% Solution Ratio

    fahim5466Earliest, Jul '17

    Fake_DeathFastest, 101701.4s

    avivillaLightest, 918 kB

    fahim5466Shortest, 596B

    Submit

    Login to submit

    Editorial

    Contact with Bishwajit Purkaystha.