Restaurant Reservations: Minimum Number of Tables

You are given an array of reservation time intervals where each reservation is represented as a pair of integers in the 24-hour format. For example, an interval (900, 1100) represents a reservation starting at 9:00 and finishing at 11:00. Reservations that end exactly when another begins do not overlap. Your task is to determine the minimum number of tables required so that all reservations can be accommodated without any time conflicts.

Input Format: The input begins with an integer T representing the number of test cases. Each test case starts with an integer n, the number of reservations, followed by n lines, each containing two integers representing the start time and end time of a reservation.

Output Format: For each test case, output a single integer representing the minimum number of tables required to handle all reservations.

The problem can be mathematically described as follows. Given a set of intervals \( [s_i,e_i) \), we need to compute the maximum number of overlapping intervals at any time, which is given by:

[ \max_{t} \sum_{i=1}^{n} \mathbf{1}_{[s_i,e_i)}(t), ]

where \( \mathbf{1}_{[s_i,e_i)}(t) \) is the indicator function that is 1 if \( t \) lies within the interval \( [s_i,e_i) \) and 0 otherwise.

inputFormat

The first line of input contains an integer T, the number of test cases. Each test case consists of the following:

1. An integer n representing the number of reservations.
2. n subsequent lines, each containing two space-separated integers representing the start time and end time of a reservation.

For example:

4
3
900 1100
1000 1200
1100 1300
2
1400 1500
1500 1600
3
800 900
850 905
900 1000
1
1215 1315

outputFormat

For each test case, output a single integer on a new line which is the minimum number of tables required to accommodate all reservations.

2
1
2
1

## sample

4
3
900 1100
1000 1200
1100 1300
2
1400 1500
1500 1600
3
800 900
850 905
900 1000
1
1215 1315

2
1
2
1

</p>