B. Zhily and Mex and Max
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Deeper in the wilderness, Zhily and Jily discovered a mysterious sequence of numbers. Each prefix of the sequence has an important characteristic value, known as the mex and the max. By rearranging the sequence, it can generate a special kind of magic.

You are given an array $$$a$$$ of $$$n$$$ non-negative integers. You can rearrange it arbitrarily.

Find the maximum possible value of the sum of the MEX$$$^{\text{∗}}$$$ and the maximum value over all prefixes. Formally, you need to maximize the following expression: $$$\sum\limits_{i=1}^n (\operatorname{mex}(a_1,a_2,\cdots,a_i)+\max(a_1,a_2,\cdots,a_i))$$$.

$$$^{\text{∗}}$$$The minimum excluded (MEX) of a collection of integers $$$c_1, c_2, \ldots, c_k$$$ is defined as the smallest non-negative integer $$$x$$$ which does not occur in the collection $$$c$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n$$$ ($$$0\leq a_i \leq 10^9$$$) — the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output the maximum sum on a new line.

Example
Input
5
5
0 0 0 0 0
2
0 1
5
1 1 1 1 0
6
1 1 4 5 1 4
1
1000000000
Output
5
4
13
30
1000000000
Note

In the first test case, no matter how you rearrange $$$a$$$, the MEX and the maximum value for each prefix will always be $$$1$$$ and $$$0$$$, respectively.

In the third test case, you can rearrange $$$a$$$ into $$$[0,1,1,1,1]$$$, so that $$$\sum\limits_{i=1}^n (\operatorname{mex}(a_1,a_2,\cdots,a_i)+\max(a_1,a_2,\cdots,a_i))=(1+0)+(2+1)+(2+1)+(2+1)+(2+1)=13$$$. It can be shown that this is the optimal solution.