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

У Sho есть массив $$$a$$$ состоящий из $$$n$$$ целых чисел. За одну операцию Sho может выбрать два различных индекса $$$i$$$ и $$$j$$$, после чего удалить из массива элементы $$$a_i$$$ и $$$a_j$$$.

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

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

Более формально, после всех операций массив Sho удовлетворяет двум следующим критериям:

  • В массиве не существует таких пар индексов, что $$$i < j$$$ и $$$a_i = a_j$$$.
  • Длина массива $$$a$$$ максимальна.
Выведите длину оставшегося у Sho массива.
Входные данные

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

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

Вторая строка каждого набора данных содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \leq a_i \leq 10^4$$$) — элементы начального массива.

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

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

Пример
Входные данные
4
6
2 2 2 3 3 3
5
9 1 9 9 1
4
15 16 16 15
4
10 100 1000 10000
Выходные данные
2
1
2
4
Примечание

В первом наборе данных Sho может сделать следующие операции:

  1. Выбрать индексы $$$1$$$ и $$$5$$$. Тогда массив станет $$$[2, 2, 2, 3, 3, 3] \rightarrow [2, 2, 3, 3]$$$.
  2. Выбрать индексы $$$1$$$ и $$$4$$$. Тогда массив станет $$$[2, 2, 3, 3] \rightarrow [2, 3]$$$.
Финальный массив имеет длину $$$2$$$, так что ответом является $$$2$$$. Можно доказать, что Sho не может получить массив большей длины.

Во втором наборе данных Sho может сделать следующие операции:

  1. Выбрать индексы $$$3$$$ и $$$4$$$. Тогда массив станет $$$[9, 1, 9, 9, 1] \rightarrow [9, 1, 1]$$$.
  2. Выбрать индексы $$$1$$$ и $$$3$$$. Тогда массив станет $$$[9, 1, 1] \rightarrow [1]$$$.
Финальный массив имеет длину $$$1$$$, так что ответом является $$$1$$$. Можно доказать, что Sho не может получить массив большей длины.