C. Candy Shop
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Students aren't allowed to leave the Institute of Magic and Embarrassment (IME), so they get very hungry for candy. Camelo realized this opportunity and decided to open a candy store inside IME (no one knows how he got permission to do such an absurd thing).

There are $$$n$$$ students in IME, and every day student $$$i$$$ orders $$$c_i$$$ candies. Camelo does not care about money, he only wants to be liked by the maximum number of people at IME. A student likes Camelo if at the moment he receives his order, he has more candies than everyone else together.

Can you help Camelo find the maximum number of people he can make like him, and the minimum number of candies to do so? He can attend the orders in any order he wants (he may also choose to ignore some orders).

Input

The first line contains a single integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$ — the number of test cases.

Each test case is two lines and the first line contains an integer $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ indicating the number of students at IME.

The second line contains $$$N$$$ integers $$$x_i$$$ $$$(1 \leq x_i \leq 10^9)$$$, indicating how many candies student $$$i$$$ orders.

It is guaranteed that the sum of $$$N$$$ over all testcases does not exceed $$$3 \times 10^5$$$.

Output

For each test case, output two integers — the maximum number of people Camelo can make like him and the minimum number of candies to do so.

Example
Input
4
3
3 4 2
5
1 8 4 2 10
1
10
5
2 2 2 2 2
Output
2 5
4 15
1 10
1 2
Note

In the first case, we can at most make two people happy, and the way of doing so that minimizes the number of candy is attending the third person and then the first, requiring $$$2 + 3 = 5$$$ candies.