A. Goals, Goals! Everywhere
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Ammar's football team consists of $$$n$$$ players. The last match was incredible, and player $$$i$$$ contributed to scoring $$$a_i$$$ goals.

A contribution is either scoring a goal or assisting in scoring. A goal is scored by exactly one player, and at most one player can assist in scoring it. A player can't score and assist in scoring the same goal.

Determine the minimum and maximum number of goals that can be scored.

Input

The first line contains one integer $$$t \: (1 \le t \le 10^3)$$$ — the number of test cases.

The first line of each test case consists of a single integer $$$n \: (1 \le n \le 3 \cdot 10^5)$$$ — the number of players in Ammar's team.

The second line of each testcase consists of $$$n$$$ integers $$$a_i \: (0 \le a_i \le 10^9)$$$ — the contribution of each player.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output

For each testcase, output two integers: the minimum and maximum number of goals that can be scored.

Example
Input
3
3
5 2 6
1
10
5
59 35 12 64 12
Output
7 13
10 10
91 182
Note

Consider the first testcase. The maximum number of goals is the sum of all contributions, which is $$$13$$$.

The minimum number of goals is $$$7$$$ goals. The third player scores $$$6$$$ goals, each assisted by either the first or the second player, not both, leaving one contribution which is considered a goal.