Maximum Non-Overlapping Workshops

You are given multiple test cases. In each test case, there are several workshops, each with a starting time and an ending time. Your task is to determine the maximum number of workshops that can be attended by a single attendee without any overlapping schedules.

Two workshops with time intervals \( (s_i, e_i) \) and \( (s_j, e_j) \) do not overlap if \( s_j \ge e_i \). The goal is to select the maximum number of workshops such that this condition is maintained.

Constraints:

• 1 \( \leq T \leq 10 \) where T is the number of test cases.
• 0 \( \leq n \leq 10^5 \) where n is the number of workshops in a test case.
• 1 \( \leq s_i, e_i \leq 10^9 \)

It is recommended to use a greedy algorithm by sorting the workshops by their end times.

inputFormat

The input is given via standard input (stdin) and has the following format:

T
n_1
s_11 e_11
s_12 e_12
... 
n_2
s_21 e_21
s_22 e_22
...
...

</p>

Where:

• T is the number of test cases.
• For each test case, the first integer n denotes the number of workshops.
• The next n lines each contain two integers representing the start time and end time of a workshop.

outputFormat

For each test case, output a single integer on a new line representing the maximum number of non-overlapping workshops that can be attended.

## sample

3
3
1 4
2 5
3 6
4
1 3
2 4
3 5
4 6
2
1 2
2 3

1
2
2

</p>