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

Заданы $$$n$$$ положительных целых чисел $$$a_1, a_2, \dots, a_n$$$. За один ход можно выбрать произвольное четное значение $$$c$$$ и поделить на два все элементы, которые равны $$$c$$$.

Например, если $$$a=[6,8,12,6,3,12]$$$ и выбрать $$$c=6$$$, то после совершения хода $$$a$$$ примет вид: $$$a=[3,8,12,3,3,12]$$$.

Вам требуется найти минимальное количество ходов, чтобы сделать все числа в $$$a$$$ нечетными (т.е. не делящимися нацело на $$$2$$$).

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

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

Первая строка набора входных данных содержит $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — количество чисел в заданной последовательности $$$a$$$. Вторая строка содержит положительные целые числа $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Сумма значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$2\cdot10^5$$$.

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

Выведите $$$t$$$ строк — ответы для заданных наборов входных данных в порядке их следования в тесте. Ответ равен минимальному количеству ходов, чтобы сделать все числа в наборе входных данных нечетными (то есть, которые не делятся на $$$2$$$).

Пример
Входные данные
4
6
40 6 40 3 20 1
1
1024
4
2 4 8 16
3
3 1 7
Выходные данные
4
10
4
0
Примечание

В первом наборе входных данных последовательность действий может быть такая:

  • до совершения ходов $$$a=[40, 6, 40, 3, 20, 1]$$$;
  • выберем $$$c=6$$$;
  • теперь $$$a=[40, 3, 40, 3, 20, 1]$$$;
  • выберем $$$c=40$$$;
  • теперь $$$a=[20, 3, 20, 3, 20, 1]$$$;
  • выберем $$$c=20$$$;
  • теперь $$$a=[10, 3, 10, 3, 10, 1]$$$;
  • выберем $$$c=10$$$;
  • теперь $$$a=[5, 3, 5, 3, 5, 1]$$$ — все числа нечётные.

Таким образом, все числа стали нечётными за $$$4$$$ хода. За $$$3$$$ хода или менее сделать их все нечётными нельзя.