Schedule

There are N schedules, the i-th schedule has start time $s_i$ and end time $e_i$ (1 <= i <= N). There are some machines. Each two overlapping schedules cannot be performed in the same machine. For each machine the working time is defined as the difference between $time_{end}$ and $time_{start}$ , where time_{end} is time to turn off the machine and $time_{start}$ is time to turn on the machine. We assume that the machine cannot be turned off between the $time_{start}$ and the $time_{end}$.
Print the minimum number K of the machines for performing all schedules, and when only uses K machines, print the minimum sum of all working times.

The first line contains an integer T (1 <= T <= 100), the number of test cases. Each case begins with a line containing one integer N (0 < N <= 100000). Each of the next N lines contains two integers $s_i$ and $e_i$ $(0 <= s_i < e_i <= 1e9)$.

For each test case, print the minimum possible number of machines and the minimum sum of all working times.

1
3
1 3
4 6
2 5

2 8

2017 Multi-University Training Contest - Team 10