D. Эпическая трансформация
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$a$$$ длины $$$n$$$, состоящий из целых чисел. Вы можете применять следующую операцию, состоящую из нескольких шагов, над массивом $$$a$$$ ноль или более раз:

  • вы выбираете два различных числа в массиве $$$a_i$$$ и $$$a_j$$$;
  • вы удаляете $$$i$$$-й и $$$j$$$-й элементы из массива.

Например, если $$$n=6$$$ и $$$a=[1, 6, 1, 1, 4, 4]$$$, то вы можете произвести следующую последовательность операций:

  • выбираем $$$i=1, j=5$$$. Массив $$$a$$$ становится равным $$$[6, 1, 1, 4]$$$;
  • выбираем $$$i=1, j=2$$$. Массив $$$a$$$ становится равным $$$[1, 4]$$$.

Каким может быть минимальный размер массива после применения к нему некоторой последовательности операций?

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.

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

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

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

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