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

Дан массив $$$a$$$ из $$$n$$$ положительных целых чисел.

За одну операцию вы можете выбрать любую пару индексов $$$(i, j)$$$ такие, что $$$a_i$$$ и $$$a_j$$$ имеют различную четность, а затем заменить меньший из них на их сумму. Более формально:

  • Если $$$a_i < a_j$$$, замените $$$a_i$$$ на $$$a_i + a_j$$$;
  • В противном случае замените $$$a_j$$$ на $$$a_i + a_j$$$.

Найдите минимальное количество операций, необходимых для того, чтобы все элементы массива имели одинаковую четность.

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

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

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

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

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

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

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

Пример
Входные данные
7
5
1 3 5 7 9
4
4 4 4 4
3
2 3 4
4
3 2 2 8
6
4 3 6 1 2 1
6
3 6 1 2 1 2
5
999999996 999999997 999999998 999999999 1000000000
Выходные данные
0
0
2
4
3
3
3
Примечание

В первом наборе входных данных все числа уже имеют одинаковую четность, поэтому совершать операции не требуется.

В третьем наборе входных данных мы можем выполнить две операции $$$(1, 2)$$$ и $$$(1, 3)$$$. Массив $$$a$$$ преобразуется следующим образом: $$$a = [\color{red}2, \color{red}3, 4] \longrightarrow [\color{red}5, 3, \color{red}4] \longrightarrow [5, 3, 9]$$$.

В четвертом наборе входных данных примером оптимальной последовательности операций является $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(1, 4)$$$ и $$$(1, 4)$$$. Массив $$$a$$$ преобразуется следующим образом: $$$a = [\color{red}3, \color{red}2, 2, 8] \longrightarrow [\color{red}3, 5, \color{red}2, 8] \longrightarrow [\color{red}3, 5, 5, \color{red}8] \longrightarrow [\color{red}{11}, 5, 5, \color{red}8] \longrightarrow [11, 5, 5, 19]$$$.