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

В 2077 году среди роботов в моду начало попадать все подряд, даже массивы...

Будем называть массив целых чисел $$$a$$$ модным, если $$$\min(a) + \max(a)$$$ делится на $$$2$$$ без остатка, где $$$\min(a)$$$ — значение минимального элемента массива $$$a$$$, а $$$\max(a)$$$ — значение максимального элемента массива $$$a$$$.

Вам дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$. За одну операцию вы можете удалить любой элемент этого массива. Ваша задача определить, за какое наименьшее количество операций можно сделать массив $$$a$$$ модным.

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

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

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

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

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

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

Пример
Входные данные
6
2
5 2
7
3 1 4 1 5 9 2
7
2 7 4 6 9 11 5
3
1 2 1
2
2 1
8
8 6 3 6 4 1 1 6
Выходные данные
1
0
2
1
1
3
Примечание

В первом наборе входных данных нужно удалить хотя бы один элемент, поскольку $$$\min(a)+\max(a)=2+5=7$$$, а $$$7$$$ не делится на $$$2$$$. А если удалить любой из элементов, то останется ровно один элемент. И тогда $$$\max(a) + \min(a)$$$ будет делиться на $$$2$$$.

Во втором наборе входных данных ничего удалять не нужно, так как $$$\min(a)+\max(a)=1+9=10$$$, а $$$10$$$ делится на $$$2$$$.

В третьем наборе входных данных можно удалить элементы со значениями $$$2$$$ и $$$4$$$, тогда $$$\min(a)+\max(a)=5+11=16$$$, а $$$16$$$ делится на $$$2$$$.