[Login|Register]
Problems

Status

Rank

Problem 1118
Guarders
Time Limit: 3000ms
Memory Limit: 65536kb
Description

There are many guarders working for a big company. Each guarder has his/her own work time interval. For example, Yinghua always works from 11:15 to 19:34 every day and Qiming works from 22:14 to 05:13 of the morrow.

Note that the time intervals may span two days, but the lengths of them will be strictly less than 24 hours.

Two guarders can talk with each other with walkie-talkie, if and only if their work time intervals overlap. Note that only having common beginning or ending point doesn't count. For example, the interval (11:15, 19:34) overlaps with the interval (19:33, 20:10), but (11:15, 19:34) doesn't overlap with (19:34, 11:15).

Now a large event in that big company needs as many guarders as possible such that any two of them can talk with each other at some time in their work time intervals.

You are to find the maximum number of guarders who can participate in the event.

Input

The input consists of multiple test cases. Each test case starts with a line containing one integers N (1 <= N <= 1000), which is the number of guarders in the company.

Each of the following N lines gives a work time interval of a guarder in the form of "ab:cd-ef:gh", where "ab:cd" and "ef:gh" are beginning time and ending time written in the 24-hour notation.

You can assume that the input times are legal and the beginning and ending times are different.

The last test case is followed by a line containing one zero.

Output
For each test case, print a line containing the test case number (beginning with 1) followed by a integer which is the maximum number of guarders who can participate in the event.
Sample Input
3
21:59-00:43
00:42-13:03
12:00-22:00
3
21:59-21:58
21:58-21:59
21:58-05:08
0
Sample Output
Case 1: 3
Case 2: 2
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.6ms with 1 query(s).