L. Terabyte Connection
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
The secret of getting ahead is getting started. The secret of getting started is breaking your complex overwhelming tasks into small manageable tasks, and then starting on the first one.
— Mark Twain, The Adventures of Tom Sawyer

HC sends you a link to an urgent file. The file is too large to download it singly, so you decide to download it in chunks.

Assume that the file is divided into $$$n$$$ chunks. For the $$$i$$$-th chunk, it will be successfully connected at moment $$$p_i$$$, then it will take exactly $$$t_i$$$ seconds to download.

Determine the moment $$$P$$$ when all chunks are successfully connected and the moment $$$F$$$ when all chunks finish downloading.

Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10 ^ 4)$$$, denoting the number of test cases.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 2 \times 10 ^ 5)$$$.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$p_i$$$, $$$t_i$$$ $$$(1 \leq p_i, t_i \leq 10^9)$$$.

It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \times 10 ^ 5$$$.

Output

For each test case, output two integers $$$P$$$, $$$F$$$, denoting the moment when all chunks are successfully connected and the moment when all chunks finish downloading.

Example
Input
2
1
1 1
3
2 3
1 1
3 2
Output
1 2
3 5
Note

In the first test case, there is only $$$1$$$ chunk. Evidently, $$$P=1$$$, $$$F=2$$$.

In the second test case, there are $$$3$$$ chunks.

  1. At moment $$$1$$$, chunk $$$2$$$ is successfully connected;
  2. At moment $$$2$$$, chunk $$$1$$$ is successfully connected, and chunk $$$2$$$ finishes downloading;
  3. At moment $$$3$$$, chunk $$$3$$$ is successfully connected;
  4. At moment $$$5$$$, chunk $$$1$$$ and chunk $$$3$$$ finish downloading.

Therefore, $$$P=3$$$, $$$F=5$$$.