问题 6729 --最小操作数

6729: 最小操作数★★★

时间限制: 2 Sec  内存限制: 256 MB
提交: 23  解决: 9
[提交][状态][命题人:]

题目描述

你给定了一个正整数数组a[1],a[2],…,a[n]。
为使数组中所有数字的乘积(即a[1]*a[2]*…*a[n])能被2^n整除。
你可以执行以下操作任意次:
任意选择一个索引i(1≤i≤n)并将a[i]的值替换为a[i]*i。
你不能对单个索引重复应用操作。换句话说,所有选择的i值必须不同。
找到使数组中所有元素乘积可被2^n整除所需的最小操作数。请注意,这样的操作集并不总是存在。

输入

第一行包含一个整数t(1≤t≤10^4) — 测试用例的数量。
然后是输入数据集的描述。
每个测试用例的第一行包含一个整数n(1≤n≤2*10^5) — 数组a的长度。
每个测试用例的第二行包含恰好n个整数:a[1],a[2],…,a[n](1≤a[i]≤10^9)。
保证在所有测试中n值的总和不超过2*10^5。

输出

对于每个测试用例,输出使数组中所有数字的乘积(即a[1]*a[2]*…*a[n])能被2^n整除的最小操作数。如果答案不存在,则输出-1。
样例输入
Copy
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
样例输出
Copy
0
1
1
-1
2
1

提示

来源

[提交][状态]