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

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 *s _{i}* and finish at time

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 ** s_{j} > s_{i}** and

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
*s _{i}* and

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.

Input | Output |
---|---|

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 |

68% Solution Ratio

fahim5466Earliest,

Fake_DeathFastest, 101701.4s

avivillaLightest, 918 kB

fahim5466Shortest, 596B

Login to submit