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

By meem_sust13 · Limits 1s, 512 MB

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

InputOutput
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 23:50 02:10. It means this class starts at 23:50 at midnight and ends before 02:10 of the following day.

As end time is exclusive, in the second test case, the first class schedule 08:00 08:45 means that, this class starts at 8 and ends just before 08:45 and thus the two classes in the second test case does not collide and only one class room is enough.



Discussion
Statistics

54% Solution Ratio

asma_chyEarliest, 1w ago

BSMRSTU_SurvivFastest, 0.1s

Wojciech.324122Lightest, 131 kB

mdvirusShortest, 542B

Submit

Login to submit