Maximum Overlapping Employee Shifts

Given a list of employee shift intervals for multiple test cases, determine the maximum number of employees that are working simultaneously at any given moment. Each test case starts with an integer denoting the number of shifts, followed by that many lines each containing two integer values representing the start and end times of the shifts. Two shifts are considered overlapping if they share time such that the start of one shift is strictly less than the end of another, i.e. if an employee finishes at time \(t\) and another starts at \(t\), they do not overlap.

The input is provided via standard input (stdin) and the output should be printed to standard output (stdout). Ensure that your solution reads from stdin and writes to stdout.

Note: When intervals have the same time points, the end event is processed before the start event to avoid counting non-overlapping shifts as overlapping, i.e., if two shifts, one ending at \(t\) and one starting at \(t\), are given, they are not overlapping.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. For each test case, the first line contains an integer \(N\) indicating the number of intervals. The following \(N\) lines each contain two integers representing the start and end times of a shift.

Example:

2
3
1 4
2 6
8 10
4
1 2
2 3
3 4
4 5

outputFormat

For each test case, output a single integer on a new line representing the maximum number of overlapping employee shifts detected.

Example:

2
1

## sample

2
3
1 4
2 6
8 10
4
1 2
2 3
3 4
4 5

2
1

</p>