Schedule

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 153428/153428 K (Java/Others)

Description

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.

Input

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)$.

Output

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

Sample Input

1 3 1 3 4 6 2 5

Sample Output

2 8

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码