Maximum Non-overlapping Intervals

You are given several test cases, each consisting of a set of intervals representing marathons. Each interval is described by its start time and end time. Two intervals \((s_i, f_i)\) and \((s_j, f_j)\) are considered non-overlapping if and only if \(s_j \geq f_i\). Your task is to determine the maximum number of non-overlapping intervals that can be chosen for each test case.

This problem can be solved using a greedy algorithm. First, sort the intervals by their end times. Then, iteratively choose the interval with the earliest finish time that does not overlap with the previously selected interval. This approach guarantees an optimal solution.

inputFormat

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

• The first line contains an integer \(T\) representing the number of test cases.
• For each test case, the first line contains an integer \(N\) representing the number of intervals.
• The following \(N\) lines each contain two space-separated integers \(S\) and \(E\), representing the start and end times of an interval.

outputFormat

For each test case, output a single integer on a new line to standard output (stdout) representing the maximum number of non-overlapping intervals.

## sample

5
3
1 2
2 4
3 5
4
3 4
2 3
1 2
5 6
4
1 10
2 3
4 5
6 7
3
1 2
2 3
1 3
3
2 3
1 2
3 4

2
4
3
2
3

</p>