题目描述

乐柠兔收集了一排能量水晶，一共有 $n$ 颗，它们的能量值分别为： $a_1,a_2,\dots,a_n$

每一颗能量水晶的能量值都是一个正整数。

乐柠兔希望通过强化操作，使得 所有能量水晶能量值的乘积： $a_1 \cdot a_2 \cdot \dots \cdot a_n$

能够被 $2^n$ 整除。

为此，乐柠兔可以进行如下操作（可以进行多次）：

• 选择一个下标 $i$（$1\le i\le n$），

• 将第 $i$ 颗水晶的能量值修改为：

  $$a_i \leftarrow a_i \cdot i$$

但需要注意的是：

每一个下标 $i$ 最多只能被选择一次，也就是说，不能对同一颗水晶重复进行强化操作。

你的任务是：

计算最少需要进行多少次强化操作，才能使所有能量水晶的乘积可以被 $2^n$ 整除。

如果无论如何都无法完成目标，则输出 $-1$。

本题包含多组测试数据。

输入格式

第一行输入一个整数 $t$（$1\le t\le 10^4$），表示测试用例的数量。

接下来是 $t$ 组测试数据，每组格式如下：

• 第一行输入一个整数 $n$（$1\le n\le 2\times10^5$），表示能量水晶的数量；

• 第二行输入 $n$ 个整数： $a_1,a_2,\dots,a_n \quad (1\le a_i\le 10^9)$

保证所有测试用例中 $n$ 的总和不超过 $2\times10^5$，即：

输出格式

对于每个测试用例，输出一行一个整数：

• 表示使得所有能量水晶的能量乘积能够被 $2^n$ 整除所需的 最少强化次数；
• 如果不存在任何可行方案，输出：

-1

样例

样例输入

3
1
2
2
3 2
3
10 6 11

样例输出

0
1
1

样例说明

• 在第一个测试用例中，所有能量水晶的乘积初始值为 $2$，已经可以被 $2^1$ 整除，因此不需要进行任何强化操作。
• 在某些测试用例中，即使对所有水晶进行强化，也无法使乘积满足条件，此时答案为 $-1$。

数据范围与约定

对于 $100$ 的测试数据，保证：

• $1\le t\le 10^4$
• $1\le n\le 2\times10^5$
• $1\le a_i\le 10^9$
• $\sum n \le 2\times10^5$