问题描述

在一个被黑暗笼罩的王国里，星辰的光辉正在逐渐消失，只有依靠光明守护者们的力量，才能保卫这片土地。每个守护者都掌握着一种特殊的能力，能够使星光更加明亮。它们的能力与它们守护的星星的编号相关。每当一个守护者将自己的编号与星辰结合时，星光会被增强。

王国的命运掌握在你的手中。你作为光明的守护者之一，需要使星辰的总光辉（即所有守护者的能力乘积）能够被 $2^n$ 整除。

你可以选择一个守护者的编号 $i$ $(1≤i≤n)$，并将他 / 她的能力增强为 $a_i=a_i⋅i$。但是，每次你只能选择一个不同的编号进行增强，不能对同一个编号重复操作。

现在，求出为了使星辰的光辉能够被 $2^n$ 整除，所需的最少操作次数。

输入格式

• 第一行包含一个整数 $t\ (1 ≤ t ≤ 10)$，表示样例的组数。
• 接下来的每组样例包含两行：
  • 第一行输入一个整数 $n$，表示光明守护者的数量 $( 1≤n≤10^5)$。
  • 第二行输入 $n$ 个正整数，表示每个守护者的初始能力 $a_1,a_2,…,a_n$ $(1≤a_i≤10^9)$。

所有测试用例的 $n$ 的总和不超过 $10^5$。

输出格式

对于每组样例，输出一个整数，表示使星辰的光辉能被 $2^n$ 整除所需的最小操作次数。如果无法实现，输出 $-1$。

样例输入

4
1
2
2
3 2
3
10 6 11
4
13 17 1 1

样例输出

0
1
1
-1

说明

样例1解释

在第一个测试用例中，所有元素的乘积是 $2$ ， 能够被 $2^1$ 整除，因此不需要任何操作。

在第二个测试用例中，所有元素的乘积是 $6$ ， 不能被 $2^2$ 整除，我们可以对 $2$ 号进行增强，让 $a_2=a_2*2=4$，现在所有元素的乘积是 $12$ ， 能够被 $2^2$ 整除，因此需要 $1$ 次操作。

在第四个测试用例中，我们即使增强所有守护者，仍然无法使所有数的乘积能被 $2^4$ 整除，因此输出 $-1$。