No submission language available for this problem.

Background

Special for beginners, ^_^

Description

You are given an array of positive integers $a_1,a_2,…,a_n$.

Make the product of all the numbers in the array (that is, $a_1⋅a_2⋅…⋅a_n$) divisible by $2^n$.

You can perform the following operation as many times as you like:

• select an arbitrary index $i$ ($1≤i≤n$) and replace the value $a_i$ with $a_i=a_i⋅i$.

You cannot apply the operation repeatedly to a single index. In other words, all selected values of $i$ must be different.

Find the smallest number of operations you need to perform to make the product of all the elements in the array divisible by $2^n$.

Note that such a set of operations does not always exist.

Format

Input

The first line of the input contains a single integer $t$ ($1≤t≤10^4$) — the number test cases.

Then the descriptions of the input data sets follow.

The first line of each test case contains a single integer $n$ ($1≤n≤2⋅10^5$) — the length of array $a$.

The second line of each test case contains exactly $n$ integers: $a_1,a_2,…,a_n$ ($1≤a_i≤10^9$).

It is guaranteed that the sum of $n$ values over all test cases in a test does not exceed $2⋅10^5$.

Output

For each test case, print the least number of operations to make the product of all numbers in the array divisible by $2^n$. If the answer does not exist, print $-1$.

Samples

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

Note

In the first test case, the product of all elements is initially $2$, so no operations needed.

In the second test case, the product of elements initially equals $6$. We can apply the operation for $i=2$, and then $a_2$ becomes $2⋅2=4$, and the product of numbers becomes $3⋅4=12$, and this product of numbers is divided by $2^n=2^2=4$.

In the fourth test case, even if we apply all possible operations, we still cannot make the product of numbers divisible by $2^n$ — it will be $(13⋅1)⋅(17⋅2)⋅(1⋅3)⋅(1⋅4)=5304$, which does not divide by $2^n$=$2^4$=$16$.

In the fifth test case, we can apply operations for $i$=$2$ and $i$=$4$.

Limitation

1s, 1024KiB for each test case.