Total Productive Hours

You are given the work logs of several employees. Each employee's work log is a list of intervals, where each interval is represented by its starting hour and ending hour. Some intervals may overlap. For each employee, you must calculate the total number of productive hours by merging overlapping intervals. The productive hours for an interval is computed as the difference between its end and start time.

Note: If two intervals overlap, they should be merged into a single interval. The final productive hours are the sum of the lengths of these merged intervals.

For example, if an employee has intervals [9, 11] and [10, 12], these merge into [9, 12] and the productive hours are 3 hours.

inputFormat

The first line of the input contains an integer T, the number of employees.

For each employee, the first line contains an integer N, the number of log intervals for that employee. This is followed by N lines, each containing two space-separated integers S and E, representing the start and end times of a log interval.

All inputs are given via standard input (stdin).

outputFormat

Output a single line containing T integers separated by spaces. The i-th integer should be the total productive hours for the i-th employee. Write your output to standard output (stdout).

2
3
9 11
10 12
14 16
2
8 12
11 15

5 7