Maximum Non-overlapping Acts

You are given a set of acts, each with a start time and an end time. Your task is to determine the maximum number of non-overlapping acts that can be scheduled.

Problem Details:

• The acts are represented by their start and end times.
• You must select acts such that no two selected acts overlap.
• The optimal solution uses a greedy strategy based on sorting by the finish times.

Hint: It is optimal to always select the act that finishes the earliest.

The input will consist of multiple test cases. For each test case, you have to compute the maximum number of non-overlapping acts possible.

inputFormat

The first line of input contains an integer T representing the number of test cases. For each test case:

1. The first line contains an integer n, the number of acts.
2. The following n lines each contain two space-separated integers representing the start and end time of an act.

Input is provided via standard input (stdin).

outputFormat

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

Output is written to standard output (stdout).

## sample

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

2
4

</p>