Schedule

There are $N$ tasks: task $i$ has to start at moment $s_i$ and finish at moment $e_i$. There is a potentially infinite supply of machines. We want to assign tasks to machines. Each task is assigned to one machine. A machine may handle any number of tasks as long as no two of them overlap. Tasks $i$ and $j$ are said to overlap if the intersection of the open intervals $(s_i, e_i)$ and $(s_j, e_j)$ is non-empty.

A machine is turned on at the moment when the earliest of its assigned tasks has to start, and turned off at the moment when the latest of them has to finish. The working time of a machine is the length of the time period between these two moments: a single machine can be turned on and off only once.

Find the minimum possible number of machines $K$ such that we can perform all tasks using only $K$ machines. Also, when using $K$ machines, find the minimum possible sum of all their working times.

The first line of input contains an integer $T$, the number of test cases ($1 \le T \le 100$).

Each test case begins with a line containing one integer $N$ ($0 < N \le 10^5$). Each of the next $N$ lines contains two integers $s_i$ and $e_i$ ($0 \le s_i < e_i \le 10^9$).

It is guaranteed that $N > 50$ for no more than 10 test cases.

For each test case, print two integers in one line: the minimum possible number of machines $K$ to perform all tasks and the minimum sum of all working times when using $K$ machines.