[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 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$.

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

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

• select an arbitrary index 𝑖$i$ (1≤𝑖≤𝑛$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𝑛$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$ (1≤𝑡≤104$(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≤𝑛≤2⋅105$1\le n\le 2\cdot {10}^5$) — the length of array 𝑎$a$.

The second line of each test case contains exactly 𝑛$n$ integers: 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤109$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⋅105$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𝑛$2^n$. If the answer does not exist, print -1.

Note

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

In the second test case, the product of elements initially equals 6$6$. We can apply the operation for 𝑖=2$i=2$, and then 𝑎2$a_2$ becomes 2⋅2=4$2\cdot 2=4$, and the product of numbers becomes 3⋅4=12$3\cdot 4=12$, and this product of numbers is divided by 2𝑛=22=4$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𝑛$2^n$  — it will be (13⋅1)⋅(17⋅2)⋅(1⋅3)⋅(1⋅4)=5304$(13\cdot 1)\cdot (17\cdot 2)\cdot (1\cdot 3)\cdot (1\cdot 4)=5304$, which does not divide by 2𝑛=24=16$2^n=2^4=16$.

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