Maximum Non-Overlapping Projects

You are given \(T\) test cases. In each test case, you have \(N\) projects, each represented by an interval \((S, E)\) where \(S\) is the start time and \(E\) is the end time. Two projects are considered non-overlapping if the start time of one project is not earlier than the end time of the previously selected project (i.e. \(S_i \ge E_j\)).

Your task is to find the maximum number of projects you can schedule for each test case such that no two selected projects overlap.

A common greedy approach to solve this problem is to sort the projects by their ending times \(E\) and then iteratively select the projects that start after or exactly when the last selected project ended.

Example: For a project list [(1, 3), (2, 5), (4, 6)], the optimal solution is to select projects (1, 3) and (4, 6), yielding an answer of 2.

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 projects.
• The next \(N\) lines each contain two space-separated integers, \(S\) and \(E\), representing the start and end times of a project.

Input is provided via standard input (stdin).

outputFormat

For each test case, output a single line containing one integer: the maximum number of non-overlapping projects that can be selected. The output should be written to standard output (stdout).

## sample

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

2
3

</p>