Maximum Non-Overlapping Tasks

You are given several test cases where each test case contains a list of tasks. Each task has a start time and an end time. Your goal is to determine the maximum number of tasks that can be completed without overlapping. A task is completed if its start time is not less than the end time of the last selected task. Mathematically, if the end time of the last selected task is \( e_{last} \), then the next task can be selected only if its start time \( s \) satisfies \( s \ge e_{last} \).

This is a classic greedy scheduling problem that can be solved by first sorting the tasks by their end times and then selecting the tasks in order.

inputFormat

The input is read from stdin and has the following format:

T
n
s[1] e[1]
s[2] e[2]
... 
s[n] e[n]
... (repeated for T test cases)

Here, T is the number of test cases. For each test case, the first line contains an integer n, the number of tasks. This is followed by n lines each containing two integers representing the start and end times of a task.

outputFormat

For each test case, output a single line to stdout containing the maximum number of non-overlapping tasks that can be completed.

## sample

5
1
1 2
3
1 2
2 3
3 4
3
1 3
2 5
4 7
4
10 20
20 30
30 40
40 50
5
100 200
150 250
200 300
250 350
300 400

1
3
2
4
3

</p>