# Practice on Toph

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

# Mr. Xifu and His New School

After working as a teacher for a long time, Mr. Xifu has finally decided to open a new school of his own. In his school, he wants to assure the highest comfort to the teachers. He has decided that any teacher will be able to take a class at any time he wishes and the classes of this school will not have any fixed duration other than the fact that a class can’t go on for more than 24 hours. In fact, classes can be happening even at midnight and classes may go over to the next day!

All of the teachers of his school have submitted a list of the start and end times of their classes to Mr. Xifu. Minimum duration of a class is 1 minute. Now, Mr. Xifu does not want to change any of these class times but he is confused about how many classrooms he is going to need so that every class can start and end at the given times. In any single minute, if there are **X** amounts of classes running, there must be at least **X** rooms in Mr. Xifu’s school. As building too many classrooms will be too costly, he wants to know the minimum number of classrooms he is going to need so that the classes which will be running at the same time can run simultaneously without any shortage of classrooms.

As Mr. Xifu is not good at calculations, your task is to help him to calculate the minimum number of class rooms he is going to need for his school given the class schedules of the teachers.

## Input

The first line of the input contains an integer **T** (0 < T <=100), the number of test cases.

Each test case will start with an integer **N** (N is positive and sum of N over all test cases is less than or equal to 1000000).

Each of the following **N** lines will contain the start time and the end time of a class. The time will be in the format - **HH:MM**

Note that time will be given in 24-Hour format (00<=HH<24, 00<=MM<60).

The start and end times will be separated by a single space. End time is exclusive, that means, if the start time of a class is **S** and the end time of class is **E**, the class is running in the **S**-th time, but must end right before **E** time. See sample I/O explanation for better understanding.

## Output

For each test case print the minimum number of classrooms needed in the following format:

Case #**c**: Mr.Xifu needs **m** classroom(s)

where c is the number of test case and m is the answer.

## Sample

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

3 4 23:50 02:10 12:10 20:00 08:00 10:00 09:30 11:00 2 08:00 08:45 08:50 10:50 4 12:35 12:30 18:19 22:29 13:46 18:56 06:13 18:29 | Case #1: Mr.Xifu needs 2 classroom(s) Case #2: Mr.Xifu needs 1 classroom(s) Case #3: Mr.Xifu needs 4 classroom(s) |

Consider the first class schedule of the first test case which is As end time is exclusive, in the second test case, the first class schedule |

54% Solution Ratio

asma_chyEarliest,

BSMRSTU_SurvivFastest, 0.1s

Wojciech.324122Lightest, 131 kB

mdvirusShortest, 542B

Login to submit