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

Patchouli является магическим талисманом. Изначально у него $$$n$$$ магических жетонов. Их магическая сила может быть представлена положительными целыми числами $$$a_1, a_2, \ldots, a_n$$$.

Patchouli может выполнять следующие две операции с жетонами.

  • Слияние: Patchouli выбирает два жетона, убирает их и создает новый жетон с магической силой, равной сумме двух выбранных жетонов.
  • Сокращение: Patchouli выбирает жетон с четным значением магической силы $$$x$$$, удаляет его и создает новый жетон с магической силой, равной $$$\frac{x}{2}$$$.

Жетоны наиболее эффективны, когда они имеют нечетное значение магической силы. Пожалуйста, помогите Patchouli найти минимальное количество операций, необходимых ему, чтобы все жетоны имели нечетное значение магической силы.

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

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

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

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

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

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

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

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

Пример
Входные данные
4
2
1 9
3
1 1 2
3
2 4 8
3
1049600 33792 1280
Выходные данные
0
1
3
10
Примечание

В первом наборе входных данных $$$a$$$ изначально состоит только из нечетных чисел.

Во втором наборе входных данных выберите жетоны с магической силой $$$1$$$ и $$$2$$$ и выполните слияние. Теперь $$$a=[1,3]$$$, оба нечетные числа.

В третьем наборе входных данных сначала выберите жетоны с магической силой $$$2$$$ и $$$8$$$ и выполните слияние. Теперь $$$a=[4,10]$$$. Дальше выберите жетон с магической силой $$$10$$$ и выполните сокращение. Теперь $$$a=[4,5]$$$. Выберите жетоны с магической силой $$$4$$$ и $$$5$$$ и выполните слияние. Теперь $$$a=[9]$$$, а $$$9$$$ — нечетное число.

Можно показать, что вы не можете получить все магические силы нечетными числами менее чем за $$$3$$$ хода, поэтому ответ равен $$$3$$$.