Maximum Park Visitors

You are given the entry and exit times of visitors in a park in HH:MM format. Your task is to compute the maximum number of visitors present in the park at the same time.

Each test case starts with an integer indicating the number of visitors. This is followed by visitor records, each containing two strings: the entry time and the exit time. It is guaranteed that for each visitor, the entry time is strictly less than the exit time.

Important: If a visitor's exit time is the same as another's entry time, count the entry before the exit. In other words, if we define an event at time \( t \) as:

\( Event(t) = \begin{cases} +1 & \text{if a visitor arrives}, \\ -1 & \text{if a visitor departs} \end{cases} \)

then the maximum number of visitors is the maximum prefix sum of these sorted events.

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains an integer \( T \), representing the number of test cases.
• Each test case begins with an integer \( M \), the number of visitors.
• It is followed by \( M \) lines, each containing two strings separated by space. The first string is the entry time and the second is the exit time, both in HH:MM format.

outputFormat

For each test case, output a single line to standard output (stdout) containing an integer — the maximum number of visitors present in the park at the same time.

2
3
09:00 10:00
09:30 11:00
10:15 11:30
4
08:00 08:30
08:15 09:00
08:45 09:30
09:00 09:45

2
3