Minimum Lecture Halls

You are given a set of lecture requests, where each lecture is represented by an interval \( [l_i, r_i] \) (with \( l_i < r_i \)). Your task is to determine the minimum number of lecture halls required so that all lectures can be scheduled without any overlaps in the same hall.

Explanation: Two lectures \( [l_1, r_1] \) and \( [l_2, r_2] \) do not conflict if \( l_2 \ge r_1 \) or vice versa. The goal is to assign lectures to halls in such a way that the total number of halls used is minimized.

Hint: A greedy algorithm combined with a min-heap (priority queue) data structure can be used to efficiently solve this problem.

inputFormat

The input starts with an integer \( T \) representing the number of test cases. Each test case begins with an integer \( N \) indicating the number of lectures. This is followed by \( N \) lines, each containing two integers \( l_i \) and \( r_i \), which represent the start and end times of a lecture respectively.

Input Format:

T
N
l1 r1
l2 r2
... 
N
lN rN

outputFormat

For each test case, output a single integer representing the minimum number of lecture halls required. Each result should be printed on a new line.

## sample

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

2
2

</p>