Maximum Concurrent Processes

You are given several test cases. In each test case, a list of processes is provided. Each process is represented by its start time and end time. Your task is to compute the maximum number of processes that are running concurrently at any given time.

More formally, suppose a process is represented by an interval \([s, e]\), where \(s\) is the start time and \(e\) is the end time. Two processes \([s_1, e_1]\) and \([s_2, e_2]\) are considered to overlap if there exists a time \(t\) such that \(s_1 \le t < e_1\) and \(s_2 \le t < e_2\). Note that if one process ends exactly when another begins, they are not considered to be overlapping since the ending event is processed just before the starting event if the times are equal.

Hint: A common approach to solve such problems is to use the sweep line algorithm. You can treat each start time as an event that increases the active process count by 1 and each end time as an event that decreases it by 1. If two events occur at the same time, process the start event first.

inputFormat

The input is read from standard input (stdin) and is organized as follows:

T
n₁
s₁ e₁
s₂ e₂
...
sₙ₁ eₙ₁
n₂
s₁ e₁
s₂ e₂
...
...
n_T
s₁ e₁
s₂ e₂
...
sₙₜ eₙₜ

Where:

• T is the number of test cases.
• For each test case, the first line contains an integer n representing the number of processes.
• The next n lines each contain two integers s and e denoting the start and end times of a process.

outputFormat

For each test case, output a single integer on a new line representing the maximum number of processes running concurrently.

Output is written to standard output (stdout).

## sample

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

2
3
1
3
5

</p>