Schedule

Problem 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

Source

2017 Multi-University Training Contest - Team 10

https://acm.hdu.edu.cn/showproblem.php?pid=6180