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?
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 ≤ si ≤ fi ≤ 109).
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.
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
Login to submit
Contact with Bishwajit Purkaystha.