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 Specification

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 Specification

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

- A single line with
`Case #: answer`

where`#`

is the serial number of the current test case (start the numbering from 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 of Output for Sample Input

**Case 1:**We will draw two lines (parallel to Y-axis) crossing X-axis at points and . These two lines will touch all five segments.**Case 2:**We can touch all the points even with one line crossing X-axis at .**Case 3:**We will draw the first line at any point in range so that it can touch the first three lines. We will draw the 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.

Original Problem Author: shaka_shadows; Problem Resource: HackerRank

## Comments