Maximum Total Duration of Non-Overlapping Tasks

You are given (T) test cases. In each test case, you are provided with (N) tasks where each task is represented by its start time and end time as a pair ((s,e)). Your goal is to select a subset of these tasks such that no two tasks overlap (i.e. for any two selected tasks (i) and (j), the condition (s_i \ge e_j) holds if (i) is chosen after (j)) and the total duration (\sum (e-s)) is maximized.

The tasks should be selected using a greedy strategy by sorting them by their end times. This strategy ensures that you are always free to attend the next task, thereby maximizing the total duration of non-overlapping tasks.

inputFormat

The input is given via standard input (stdin). The first line contains 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. This is followed by (N) lines, each containing two space-separated integers (s) and (e), representing the start and end times of a task.

outputFormat

For each test case, output the maximum total duration of selected non-overlapping tasks. Each result should be printed on a new line to standard output (stdout).## sample

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

4
4