Maximum Non-Overlapping Intervals

You are given several test cases. In each test case, you are provided with N intervals, each defined by a start time and an end time. Your task is to determine the maximum number of non-overlapping intervals that can be selected. Two intervals are considered non-overlapping if the start time of an interval is greater than or equal to the end time of the last selected interval.

A greedy approach works well for this problem. First, sort all intervals by their end times. Then, iteratively select an interval if its start time is greater than or equal to the end time of the last selected interval. Formally, if you have a sequence (s_i, e_i) sorted by e_i, select an interval if:

\( s_i \geq E \)

where \( E \) is the end time of the previously selected interval.

This problem is a classic example of interval scheduling and can be efficiently solved using a greedy algorithm.

inputFormat

The input is given via standard input (stdin). The first line contains an integer T representing the number of test cases. For each test case, the first line contains an integer N which is the number of intervals. The next N lines each contain two integers separated by space, representing the start and end times of an interval.

Example:

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

outputFormat

For each test case, output a single line containing an integer which is the maximum number of non-overlapping intervals that can be selected. The output should be printed to standard output (stdout).

Example:

2
4

## sample

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

2
4

</p>