Problem Visual

Problem Statement

Cherry-chan has some croissants. The flavor of each croissant is represented by an integer between $1$ and $N$, inclusive, and she has $A_i$ croissants of flavor $i$.

Cherry-chan wants to eat as many croissants as possible by repeating the following action $0$ or more times: "choose $1$ croissant from those she has and eat it."

However, since Cherry-chan gets bored easily, she must obey the following rule.

• Each croissant eaten as the $2$-nd or later must have a flavor different from the croissant eaten immediately before it.

What is the maximum number of croissants Cherry-chan can eat?

Solve $T$ test cases.

Constraints

• $1 \leq T \leq 10^5$.
• Constraints for each test case
  • $1 \leq N \leq 3 \times 10^5$.
  • $1 \leq A_i \leq 10^9 \quad (1 \leq i \leq N)$.
• Constraints for each test file.
  • The sum of $N$ over the $T$ test cases is at most $3 \times 10^5$.

Input

$T$
$\textrm{Testcase}_1$
$\textrm{Testcase}_2$
$\vdots$
$\textrm{Testcase}_T$

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

Output

The output consists of $T$ lines. On line $t~(1 \leq t \leq T)$, print the answer for the $t$-th test case.

Sample

3
3
1 2 3
1
46
6
15 18 42 87 15 93

6
1
270