Minimum Meeting Rooms

You are given several test cases. Each test case consists of a list of meetings with their start and end times. Two meetings overlap if one starts before the other ends. Your task is to determine the minimum number of meeting rooms required for each test case so that all meetings can be held without any time conflicts.

More formally, if a meeting is represented as a pair \( (S, E) \), where \( S \) is the start time and \( E \) is the end time (with \( S < E \)), then two meetings \( (S_1, E_1) \) and \( (S_2, E_2) \) overlap if \( S_1 < E_2 \) and \( S_2 < E_1 \). The goal is to compute, for each test case, the minimum number of rooms required so that no two overlapping meetings are scheduled in the same room.

Hint: A common solution involves sorting the start and end times separately and using the two-pointer technique to track how many meetings are running concurrently.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
N1
S11 E11
S12 E12
...
S1N1 E1N1
N2
S21 E21
S22 E22
...
S2N2 E2N2
...
NT
ST1 ET1
ST2 ET2
...
STNT ETNT

Where:

• \( T \) is the number of test cases.
• For each test case, \( N \) is the number of meetings.
• Each meeting is given by its start time and end time separated by a space.

outputFormat

For each test case, output one integer on a new line representing the minimum number of meeting rooms required.

## sample

3
3
1 4
2 5
3 6
4
1 10
2 7
3 4
5 6
2
1 5
2 6

3
3
2

</p>