A. Вам нужна только посылка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для мультимножества $$$T$$$, состоящего из целых неотрицательных чисел, определим:

  • $$$\text{sum}(T)$$$ — это сумма всех элементов в $$$T$$$. Например, если $$$T = \{0,1, 1, 3\}$$$, то $$$\text{sum}(T)= 0+1+1+3=5$$$.

  • $$$\text{mex}(T)$$$ — это наименьшее целое неотрицательное число, отсутствующее в $$$T$$$. Например, если $$$T = \{0,1, 1, 3\}$$$, то $$$\text{mex}(T) = 2$$$, потому что $$$2$$$ — это наименьшее целое неотрицательное число, отсутствующее в $$$T$$$.
Вам дано мультимножество $$$S$$$ размером $$$n$$$, состоящее из целых неотрицательных чисел. Изначально ваш счет равен $$$0$$$. Вы можете выполнять следующие операции любое количество раз (возможно, ноль) в любом порядке:
  • Выберите подмножество $$$S' \subseteq S$$$ (т.е. $$$S'$$$ содержит некоторые из элементов, которые в данный момент находятся в $$$S$$$), добавьте $$$\text{sum}(S')$$$ к вашему счету, а затем удалите $$$S'$$$ из $$$S$$$.
  • Выберите подмножество $$$S' \subseteq S$$$, добавьте $$$\text{mex}(S')$$$ к вашему счету, а затем удалите $$$S'$$$ из $$$S$$$.

Найдите максимальный возможный счет, который вы можете получить.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 50$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$S_1, S_2, \ldots, S_n$$$ ($$$0 \le S_i \le 50$$$).

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальный возможный счет, который можно получить.

Пример
Входные данные
2
3
0 1 1
3
1 2 3
Выходные данные
3
6
Примечание

В первом наборе входных данных возможна такая оптимальная стратегия:

  • Выберите $$$S'=\{0,1\}$$$, добавьте $$$\text{mex}(S')=\text{mex}(\{0,1\})=2$$$ к вашему счету, а затем удалите $$$S'$$$ из $$$S$$$. В данный момент ваш счет равен $$$2$$$, и $$$S=\{1\}$$$.
  • Выберите $$$S'=\{1\}$$$, добавьте $$$\text{sum}(S')=\text{sum}(\{1\})=1$$$ к вашему счету, а затем удалите $$$S'$$$ из $$$S$$$. В данный момент ваш счет равен $$$3$$$, и $$$S=\varnothing$$$.

После этого вы не можете выполнять никаких дальнейших операций. Можно доказать, что $$$3$$$ — это максимальный возможный счет, который вы можете получить.