B. Игра с цветными шариками
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру. У них есть $$$n$$$ шариков, $$$i$$$-й из них имеет цвет $$$c_i$$$. Игроки ходят по очереди; сначала ходит Алиса, затем Боб, затем снова Алиса, затем опять Боб и так далее.

Во время своего хода игрок должен взять один из оставшихся шариков и убрать его из игры. Если шариков больше не осталось (все $$$n$$$ шариков были взяты), игра заканчивается.

Очки Алисы в конце игры рассчитываются следующим образом:

  • она получает $$$1$$$ очко за каждый цвет $$$x$$$, для которого она взяла хотя бы один шарик этого цвета;
  • дополнительно она получает $$$1$$$ очко за каждый цвет $$$x$$$, для которого она взяла все шарики этого цвета (конечно, учитываются только цвета, присутствующие в игре).

Например, предположим, что есть $$$5$$$ шариков, их цвета $$$[1, 3, 1, 3, 4]$$$, и игра проходит следующим образом: Алиса берет $$$1$$$-й шарик, затем Боб берет $$$3$$$-й шарик, затем Алиса берет $$$5$$$-й шарик, затем Боб берет $$$2$$$-й шарик, и, наконец, Алиса берет $$$4$$$-й шарик. Тогда Алиса получает $$$4$$$ очка: $$$3$$$ очка за наличие хотя бы одного шарика для цветов $$$1$$$, $$$3$$$ и $$$4$$$, и $$$1$$$ очко за наличие всех шариков цвета $$$4$$$. Обратите внимание, что эта стратегия не обязательно является оптимальной для обоих игроков.

Алиса хочет максимизировать свои очки в конце игры. Боб хочет минимизировать их. Оба игрока играют оптимально (т. е. Алиса выбирает стратегию, которая позволяет ей получить как можно больше очков, а Боб выбирает стратегию, которая минимизирует количество очков, которые может получить Алиса).

Вычислите очки Алисы в конце игры.

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

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

Каждый набор входных данных состоит из двух строк:

  • первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 1000$$$) — количество шариков;
  • вторая строка содержит $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) — цвета шариков.

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$1000$$$.

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

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

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

Во втором наборе входных данных примера цвета всех шариков различны, поэтому, независимо от того, как действуют игроки, Алиса получает $$$4$$$ очка — у нее все шарики двух цветов и ни одного шарика третьего цвета.

В третьем наборе входных данных примера цвета всех шаров одинаковы, поэтому, независимо от того, как действуют игроки, Алиса получает $$$1$$$ очко за то, что у нее хотя бы один (но не все) шарик цвета $$$4$$$.