Minimum Conference Rooms

You are given (T) test cases. In each test case, you have (N) sessions where each session is described by its start time and end time. Your task is to determine the minimum number of conference rooms required to schedule all sessions so that no two sessions that overlap in time use the same room.

A session is represented by an interval ([s, e]), and two sessions ([s_i, e_i]) and ([s_j, e_j]) are said to conflict if (s_j < e_i).

For each test case, output the minimum number of rooms needed.

inputFormat

The first line of input contains an integer (T), the number of test cases. For each test case, the first line contains an integer (N) representing the number of sessions. The next (N) lines each contain two space-separated integers representing the start and end times of a session.

outputFormat

For each test case, output a single integer on a new line — the minimum number of conference rooms required to schedule all the sessions without conflicts.## sample

1
3
30 75
0 50
60 150

2