Maximum Non-overlapping Events

You are given several events, each specified by a start time and an end time in the HH:MM format. Your task is to determine the maximum number of events that you can attend without any time conflicts.

To solve this problem, consider using a greedy algorithm approach. First, convert the event times into minutes since midnight, then sort all events by their end times. Finally, select events one by one by ensuring that the start time of the current event is not earlier than the end time of the previously selected event.

The non-overlap condition between two events can be formalized as:

$$s_i \geq e_{prev}$$

where s_i is the start time of the current event (in minutes) and e_prev is the end time of the last selected event.

inputFormat

The first line of the input contains an integer T, representing the number of test cases. For each test case, the first line contains an integer N, representing the number of events. The next N lines each contain two strings separated by a space, representing the start and end times of an event in HH:MM format.

outputFormat

For each test case, output a single line with an integer representing the maximum number of non-overlapping events that can be attended.## sample

2
3
09:00 10:30
10:00 11:00
11:00 12:00
4
09:00 10:00
10:00 11:00
10:30 11:30
11:00 12:00

2
3