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

Массив $$$b$$$ называется хорошим, если сумма элементов $$$b$$$ четная.

Вам дан массив $$$a$$$ из $$$n$$$ положительных целых чисел. За одну операцию вы можете выбрать индекс $$$i$$$ и заменить $$$a_i := \lfloor \frac{a_i}{2} \rfloor$$$. $$$^\dagger$$$

Найдите минимальное число операций (возможно, $$$0$$$), необходимое, чтобы сделать $$$a$$$ хорошим. Можно показать, что всегда возможно сделать $$$a$$$ хорошим.

$$$^\dagger$$$ $$$\lfloor x \rfloor$$$ обозначает округление вниз, то есть наибольшее число, меньшее или равное $$$x$$$. Например, $$$\lfloor 2.7 \rfloor = 2$$$, $$$\lfloor \pi \rfloor = 3$$$ и $$$\lfloor 5 \rfloor =5$$$.

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

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

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

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

Обратите внимание, что сумма значений $$$n$$$ по наборам входных данных не ограничена.

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

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

Пример
Входные данные
4
4
1 1 1 1
2
7 4
3
1 2 4
1
15
Выходные данные
0
2
1
4
Примечание

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

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

В третьем примере $$$a$$$ станет равным $$$[0,2,4]$$$, если мы выполним операцию один раз с индексом $$$1$$$. Так как $$$[0,2,4]$$$ хороший, то ответ равен $$$1$$$.

В четвертом примере нужно выполнить операцию с индексом $$$1$$$ четыре раза. После всех операций $$$a$$$ становится равным $$$[0]$$$. Можно показать, что невозможно сделать массив $$$a$$$ хорошим за меньшее число операций.