给定一个正整数数组 $$$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。
示例
输入 #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
输出 #1
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$$$ 进行运算。