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

Вы сражаетесь с боссом, у которого неизвестное количество здоровья. У вас есть набор из $$$n$$$ карт заклинаний, где $$$i$$$-я карта наносит $$$a_i$$$ единиц урона. Вы можете переставить карты в своей руке и разыграть карты в любом порядке по своему усмотрению.

У босса есть адаптивный щит. Если вы сыграете две карты подряд, наносящие одинаковое количество урона, щит активируется навсегда. Карта, вызвавшая активацию щита, по-прежнему наносит обычный урон, но все следующие карты, которые вы сыграете, будут наносить $$$0$$$ урона.

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

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

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

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

Во второй строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 1000$$$) — урон, наносимый каждой картой.

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

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

Пример
Входные данные
4
1
100
4
10 5 10 10
5
1 2 3 4 5
6
7 7 7 7 7 7
Выходные данные
100
35
15
14
Примечание

В первом наборе входных данных у вас есть только $$$1$$$ карта. Вы разыгрываете её, нанося $$$100$$$ единиц урона.

Во втором наборе входных данных вы можете упорядочить свою руку следующим образом: $$$[10, 5, 10, 10]$$$. Вы разыгрываете первую 10. Затем вы разыгрываете 5. Затем вы разыгрываете вторую 10. Затем вы разыгрываете последнюю 10. Поскольку вы разыграли две 10 подряд, активируется щит. Однако карта, которая активирует щит, всё равно наносит свой обычный урон. Общий нанесённый урон составляет $$$10 + 5 + 10 + 10 = 35$$$.

В третьем наборе входных данных все карты различны. Вы можете просто разыграть их в любом порядке, чтобы нанести сумму их урона: $$$1 + 2 + 3 + 4 + 5 = 15$$$.

В четвёртом наборе входных данных все $$$6$$$ карт наносят ровно 7 единиц урона. Независимо от того, в каком порядке вы их разыграете, ваша вторая карта будет идентична первой. Вторая карта активирует щит и нанесёт свой обычный урон, но остальные $$$4$$$ карты нанесут $$$0$$$ единиц урона. Общий нанесённый урон равен $$$7 + 7 = 14$$$.