Maximum Non-Overlapping Tasks

You are given several test cases, each containing a list of tasks. Every task is represented as a pair of integers \( (s, e) \) indicating its start time \( s \) and end time \( e \). The goal is to determine the maximum number of tasks you can perform without any overlaps. Two tasks do not overlap if the start time of one is greater than or equal to the end time of the previous task. This problem can be solved efficiently using a greedy algorithm by sorting the tasks by their end times and then selecting tasks sequentially.

Input Format: The first line contains an integer \( T \) denoting the number of test cases. For each test case, the first input line contains an integer \( N \) — the number of tasks. This is followed by \( N \) lines, each containing two integers representing the start time and end time of a task.

Output Format: For each test case, output a single line with the maximum number of non-overlapping tasks that can be chosen.

Note: Use greedy selection after sorting tasks by their end times to achieve an optimal solution.

inputFormat

The input begins with an integer \( T \) (the number of test cases). For each test case, the first line contains an integer \( N \) representing the number of tasks. The next \( N \) lines each contain two space-separated integers \( s \) and \( e \), indicating the start and end times of each task.

outputFormat

For each test case, output one integer on a new line — the maximum number of non-overlapping tasks that can be completed.

## sample

1
1
1 3

1

</p>