$O(NlogN)$ 贪心

1. 问题转化：

   • 设初始乘积为 $P = a_1 \times a_2 \times \cdots \times a_n$。
   • 我们需要 $P \times (i_1 \cdot i_2 \cdot \cdots \cdot i_k)$ 能被 $2^n$ 整除，其中 $i_j$ 是操作选择的编号。

2. 关键观察：

   • 实际上，我们只需要关心乘积中因子 2 的个数。
   • 设初始乘积 $P$ 中因子 $2$ 的个数为 $cnt$ 。
   • 我们需要通过操作增加至少 $n - cnt$ 个因子 $2$ 。

3. 操作的影响：

   • 每次选择编号 $i$ 进行操作，会额外引入因子 $2$ 的个数等于 $i$ 中因子 $2$ 的个数。
   • 例如，选择编号 $4$ 会引入 $2$ 个因子 $2$。

4. 贪心策略：

   • 计算每个编号 $i$ 能提供的因子 $2$ 的个数.
   • 将这些因子 $2$ 的个数从大到小排序，优先选择提供因子 $2$ 多的操作。
   • 累计因子 $2$ 的个数，直到达到或超过 $n - cnt$ 。

5. 特殊情况：

   • 如果初始 $cnt \geq n$，则不需要操作（输出 0 ）。
   • 如果所有操作后累计的因子 $2$ 仍然小于 $n - cnt$ ，则输出 $-1$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10;
int a[N], b[N];
bool cmp(int x, int y){
	return x>y;
}
void solve() {
	int t;
	cin >> t;
	while(t--) {
		int n;
		cin >> n;
		int ans=0;
		for(int i=1; i<=n; i++){
			cin >> a[i];
			while(a[i]%2==0){
				ans++;
				a[i]/=2;
			}
			int k=i;
			b[i] = 0; //初始化 
			while(k%2==0){
				b[i]++;
				k/=2;
			}
		}
		if(ans>=n) {
			cout << 0 << '\n';
			continue;
		}
		sort(b+1, b+1+n, cmp);
		for(int i=1; i<=n; i++){
//			cout << b[i]<<' ';
			ans+=b[i];
			if(ans>=n){
				cout << i <<'\n';
				break;
			}
		}
		if(ans<n) cout<<-1<<'\n';
	}
}
int main() {
//	ios::sync_with_stdio(false);
//	cin.tie(0), cout.tie(0);
	solve();
	return 0;
}