D. Делимость на 2^n
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив положительных целых чисел $$$a_1, a_2, \ldots, a_n$$$.

Сделайте так, чтобы произведение всех чисел массива, то есть $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n$$$, делилось на $$$2^n$$$.

Вы можете выполнять следующую операцию сколько угодно раз:

  • выберите произвольный индекс $$$i$$$ ($$$1 \leq i \leq n$$$) и замените значение $$$a_i$$$ на $$$a_i=a_i \cdot i$$$.

Вы не можете применять операцию повторно к одному индексу. Иными словами, все выбранные значения $$$i$$$ должны быть различны.

Найдите, какое наименьшее количество операций нужно выполнить, чтобы произведение всех чисел массива делилось на $$$2^n$$$. Обратите внимание, что не всегда такой набор операций существует.

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

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

Далее следуют описания наборов входных данных.

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

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

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

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

Для каждого набора входных данных выведите наименьшее количество операций, которое нужно сделать, чтобы произведение всех чисел массива делилось на $$$2^n$$$. Если ответа не существует, то выведите -1.

Пример
Входные данные
6
1
2
2
3 2
3
10 6 11
4
13 17 1 1
5
1 1 12 1 1
6
20 7 14 18 3 5
Выходные данные
0
1
1
-1
2
1
Примечание

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

Во втором наборе входных данных произведение чисел изначально равно $$$6$$$. Мы можем применить операцию для $$$i = 2$$$, и тогда $$$a_2$$$ станет равно $$$2\cdot2=4$$$, а произведение чисел станет равно $$$3\cdot4=12$$$, а это произведение чисел делится на $$$2^n=2^2=4$$$.

В четвертом наборе входных данных даже если мы применим все возможные операции, то у нас все равно не получится сделать произведение чисел кратным $$$2^n$$$  — оно будет равно $$$(13\cdot1)\cdot(17\cdot2)\cdot(1\cdot3)\cdot(1\cdot4)=5304$$$, что не делится на $$$2^n=2^4=16$$$.

В пятом наборе входных данных можно применить операции для $$$i = 2$$$ и $$$i = 4$$$.