Patchouli's Magical Talisman
Contest: Codeforces Round 796 (Div. 2)
Difficulty rating: 800
Tags: bitmasks, constructive algorithms, greedy, sortings

Patchouli is making a magical talisman. She initially has $$$n$$$ magical tokens. Their magical power can be represented with positive integers $$$a_1, a_2, \ldots, a_n$$$.

Patchouli may perform the following two operations on the tokens.

- Fusion: Patchouli chooses two tokens, removes them, and creates a new token with magical power equal to the sum of the two chosen tokens.
- Reduction: Patchouli chooses a token with an even value of magical power $$$x$$$, removes it and creates a new token with magical power equal to $$$\frac{x}{2}$$$.

Tokens are more effective when their magical powers are odd values. Please help Patchouli to find the minimum number of operations she needs to make magical powers of all tokens odd values.

Input format:
Each test contains multiple test cases.

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases. The description of the test cases follows.

For each test case, the first line contains one integer $$$n$$$ ($$$1 \leq n\leq 2\cdot 10^5$$$) — the initial number of tokens.

The second line contains $$$n$$$ intergers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the initial magical power of the $$$n$$$ tokens.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print a single integer — the minimum number of operations Patchouli needs to make all tokens have an odd value of magical power.

It can be shown that under such restrictions the required sequence of operations exists.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Test case 1:

$$$a$$$ consists solely of odd numbers initially.

Test case 2:

Choose the tokens with magical power of $$$1$$$ and $$$2$$$ and perform Fusion. Now $$$a=[1,3]$$$, both are odd numbers.

Test case 3:

Choose the tokens with magical power of $$$2$$$ and $$$8$$$ and perform Fusion. Now $$$a=[4,10]$$$.

Choose the token with magical power of $$$10$$$ and perform Reduction. Now $$$a=[4,5]$$$.

Choose the tokens with magical power of $$$4$$$ and $$$5$$$ and perform Fusion. Now $$$a=[9]$$$, and $$$9$$$ is an odd number.

It can be shown that you can not make all the magical powers odd numbers in less than $$$3$$$ moves, so the answer is $$$3$$$.

Example input:
4
2
1 9
3
1 1 2
3
2 4 8
3
1049600 33792 1280

Example output:
0
1
3
10

Editorial:
Let $$$g(x)$$$ be the maximum integer satisfying $$$2^{g(x)}|x$$$.
A greedy solution is to make one integer odd integer, and plus it to other even integers. Let $$$f(a)$$$ be the answer of an sequence $$$\{a_n\}$$$.
We can find that:
$$$f(a)=\begin{cases}\sum[g (a_i)>0]-1+\min\{g(a_i)\}& \forall i,\ g(a_i)>0 \\\sum[g (a_i)>0]&\texttt{otherwise}\end{cases}$$$
It can be shown that it is the optimal strategy.
1. if $$$\exists i,\ g(a_i)=0$$$, it takes at least one operations to turn an even integer into an odd integer. 2. if $$$\forall i,\ g(a_i)>0$$$. It be shown that $$$f(a)$$$ decreases by at most $$$1$$$ with one operation. We only prove the correctness for the first operation as an example. For the first operation, assuming we choose $$$a_i$$$ and $$$a_j$$$, let $$$a_k=a_i+a_j$$$. Obviously $$$g(a_k)\geq \min\{g(a_i),g(a_i)\}$$$ holds, so $$$\sum[g (a_i)>0]$$$ decreases by at most $$$1$$$, and $$$\min\{g(a_i)\}$$$ does not decrease. So $$$f(a)$$$ decreases by at most $$$1$$$.