Tissue Rush - Repovive Premier Round 8 | Repovive

24A. Tissue Rush

500 pts2s256 MB

There are $n$ tissue boxes. Their initial numbers of tissues are $a_1, a_2, \ldots, a_n$ .

In one operation, let $k$ be the number of boxes that are currently empty. Choose a box containing at least $k+1$ tissues and remove exactly $k+1$ tissues from it.

You may perform any number of operations, including zero. Find the minimum total number of tissues that can remain in all boxes.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Samples

Input

Case 1

4
1 1 1 1

Case 2

3
3 3 3

Explanation

Case 1

Removing one tissue empties a box. Every later operation would require at least two tissues from one box, but each remaining box contains only one. Therefore, three tissues must remain.

Case 2

First, remove two tissues from the first box and one tissue from the second box, using three operations that each remove one tissue. The amounts are now (1, 2, 3), and no box is empty yet. Empty the boxes in order by removing one, two, and three tissues. No tissues remain.

Output

Case 1

Case 2

Input

Case 1

1
7

Case 2

4
1 2 2 6

Case 3

5
2 2 2 2 5

Explanation

Case 1

Remove one tissue from the only box in each of seven operations. The box becomes empty, leaving no tissues.

Case 2

Before emptying a box, reduce the third box to one tissue and the fourth box to three tissues. The amounts are (1, 2, 1, 3). Then empty the first, second, and fourth boxes, removing one, two, and three tissues respectively. One tissue remains. Leaving zero is impossible: after two boxes become empty, any further emptying operation needs at least three tissues, but only the fourth box initially has that many.

Case 3

While every operation still removes one tissue, reduce the first three boxes to one tissue each and the fifth box to three tissues. The amounts are (1, 1, 1, 2, 3). Empty the first, fourth, and fifth boxes by removing one, two, and three tissues respectively. Two tissues remain. At most two of the boxes that initially contain two tissues can become empty, because every emptying operation after the second needs at least three tissues. Hence, at least two tissues must remain.

Output

Case 1

Case 2

Case 3

There are $n$ tissue boxes. Their initial numbers of tissues are $a_1, a_2, \ldots, a_n$ .

In one operation, let $k$ be the number of boxes that are currently empty. Choose a box containing at least $k+1$ tissues and remove exactly $k+1$ tissues from it.

You may perform any number of operations, including zero. Find the minimum total number of tissues that can remain in all boxes.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

24A. Tissue Rush

Constraints

Input

Output

Samples

24A. Tissue Rush

Constraints

Input

Output

Samples