该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述：

给定一个n个数的数组，为了使得所有元素相乘能够被2的n次方整除。 你可以选择如下方法

选择一个位置ai乘以它的下标i（1<=i<=n)。ai = ai*i

每个i只能乘一次。 找到这个需要乘的最小个数。

输入格式：

第一行一个整数t，表示有t组数据（1<=t<=10^4)

接下来每组测试数据

第一行一个正整数n表示数组元素个数(1<=n<=2*10^5)

第二行n个正整数ai。(1<=ai<=10^9)

输出格式：

一个最小数，使得所有元素乘积能被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 3 2 两个元素，要使得3 * 2被2^2整除 还需要让2 * 2 所以需要乘一个i=2. 所以结果为1

O(t*nlogn)可AC