← 返回题目列表

Codeforces · 1744/D

D. 被 2^n 整除

中文机器翻译题面 查看原题

给定一个正整数数组 $$$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$$$ 进行运算。