GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

[Solution] Divisibility by 2^n Codeforces Solution

D. Divisibility by 2^n
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of positive integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$.

Make the product of all the numbers in the array (that is, ${a}_{1}\cdot {a}_{2}\cdot \dots \cdot {a}_{n}$) divisible by ${2}^{n}$.

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

• select an arbitrary index $i$ ($1\le i\le n$) and replace the value ${a}_{i}$ with ${a}_{i}={a}_{i}\cdot 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.

Input

The first line of the input contains a single integer $t$ $\left(1\le t\le {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\le n\le 2\cdot {10}^{5}$) — the length of array $a$.

The second line of each test case contains exactly $n$ integers: ${a}_{1},{a}_{2},\dots ,{a}_{n}$ ($1\le {a}_{i}\le {10}^{9}$).

It is guaranteed that the sum of $n$ values over all test cases in a test does not exceed $2\cdot {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.

Note

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

Solution Click Below:-  👉
👇👇👇👇👇

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\cdot 2=4$, and the product of numbers becomes $3\cdot 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 $\left(13\cdot 1\right)\cdot \left(17\cdot 2\right)\cdot \left(1\cdot 3\right)\cdot \left(1\cdot 4\right)=5304$, which does not divide by ${2}^{n}={2}^{4}=16$.

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