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

Чтобы развить у юного Кевина арифметические навыки, его мать придумала следующую задачу.

Даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$, а также число $$$s$$$, изначально равное $$$0$$$. Кевин выполняет следующую операцию для $$$i = 1, 2, \ldots, n$$$ по порядку:

  • Добавить $$$a_i$$$ к $$$s$$$. Если полученное $$$s$$$ чётное, Кевин зарабатывает очко, а затем делит $$$s$$$ на $$$2$$$ до тех пор, пока оно не станет нечётным.

Обратите внимание, что Кевин может заработать не более одного очка за операцию, даже если он сделал больше одного деления.

Поскольку операции деления считаются наиболее полезными для развития Кевина, его мать хочет переставить элементы $$$a$$$ таким образом, чтобы общее количество баллов у Кевина было максимальным. Определите максимально возможное количество баллов.

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

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

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

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

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

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

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

В первом наборе входных данных единственной перестановкой элементов $$$a$$$ является $$$[1]$$$. $$$s$$$ будет равен $$$1$$$, а Кевин не заработает очков.

Во втором наборе входных данных единственным оптимальным расположением элементов $$$a$$$ является $$$[2, 1]$$$. После операций $$$s$$$ последовательно становится равным $$$1$$$ и $$$1$$$. Кевин зарабатывает по очку в обеих операциях.

В третьем наборе входных данных одной из оптимальных перестановок элементов $$$a$$$ является $$$[2, 4, 6]$$$. После выполнения операций $$$s$$$ последовательно становится равным $$$1$$$, $$$5$$$ и $$$11$$$. Кевин заработает очко только на первой операции.