Maximum Non-overlapping Tasks

In this problem, you are given a set of tasks with starting and ending times. Each task is represented by a pair ((s, e)) where (s) is the start time and (e) is the finish time. Two tasks ((s_1, e_1)) and ((s_2, e_2)) do not overlap if and only if (s_2 \ge e_1). Your task is to determine the maximum number of non-overlapping tasks that can be completed for each test case. This problem can be solved efficiently using a greedy algorithm by sorting tasks by their finish times.

inputFormat

The input starts with an integer (T) indicating the number of test cases. For each test case, the first line contains an integer (N) representing the number of tasks. Each of the next (N) lines contains two integers representing the start time and end time of a task. All numbers are separated by spaces or newlines.

outputFormat

For each test case, output a single integer on a separate line: the maximum number of non-overlapping tasks that can be performed.## sample

1
3
1 3
2 5
4 6

2