Your Maths professor is a very nice guy, but he sometimes comes up with not so funny tasks. Today is one such day. The professor drew a bunch of parallel line segments on the board and asked the following question: "How many of these segments can be touched, even on their edges, by exactly two lines perpendicular to them?"

After a few seconds, he spoke again: "Let's make it more interesting. I will give you the starting and the ending points of segments over the X's axis; today's homework will be to answer the question I asked you above for any set of such segments". Right after the professor's words, one guy asked: "Is there any restriction over the segments' location?", and the professor replied: "Not really, they are just segments, so they can overlap in all the ways you may imagine."

Everybody started thinking of the weird and unexpected task, without getting a convincing result. Some time later, the class got over and before leaving the classroom, the professor said: "Just to take this to the ultimate limits, your final qualification will depend entirely on this task. Good luck and please, don't try to cheat, I will know if you try to do so." So, that was it! Your final Maths qualification was hooked to some play on segments stuff.

Input Format

Input consists of several test cases. The first line in the input is an integer, , denoting the number of test cases. test cases follow, each one with the following format:

  • A single line with an integer, , denoting the number of segments.

  • lines, each defining a segment with two integers, and , separated by a single white space, meaning that there is a segment going from to .

Constraints


Output Format

For each test case the output should follow the following format:

  • A single line with "Case #: answer" (without the quotes) where # is the serial number of the current test case (start the numbering by 1) and answer is the maximum number of segments you can touch as described above.

See the sample output for more details.

Sample Input

4
5
2 3
1 3
1 5
3 4
4 5
5
1 2
1 3
2 3
1 4
1 5
4
1 5
1 6
1 7
8 10
3
1 2
3 4
5 6

Sample Output

Case 1: 5
Case 2: 5
Case 3: 4
Case 4: 2

Explanation

  • Case 1: We will draw two lines (parallel to Y-axis) crossing X-axis at point and . These two lines will touch all the five segments.
  • Case 2: We can touch all the points even with one line crossing X-axis at .
  • Case 3: We will draw first line at any point in range so that it can touch first three lines. We will draw second line crossing X-axis at any of the points in range and it will touch the last line.
  • Case 4: It is not possible to touch more than two lines in this case.

Tested by: Devendra Agarwal

  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score