CF1688B.Patchouli's Magical Talisman

She is skilled in all kinds of magics, and is keen on inventing new one.

—Perfect Memento in Strict Sense

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.

她精通各种魔法，并热衷于发明新的魔法。

——《严格意义下的完美备忘录》

帕秋莉正在制作一枚魔法护符。她最初拥有 $n$ 枚魔法符文，其魔法力量可用正整数 $a_1, a_2, \ldots, a_n$ 表示。

帕秋莉可以对这些符文执行以下两种操作：

• 融合：帕秋莉选择两枚符文，移除它们，并创造一枚新符文，其魔法力量等于所选两枚符文的魔法力量之和。
• 还原：帕秋莉选择一枚魔法力量为偶数值 $x$ 的符文，移除它，并创造一枚新符文，其魔法力量为 $\frac{x}{2}$。

当符文的魔法力量为奇数值时，其效果更佳。请帮助帕秋莉计算出使所有符文的魔法力量均变为奇数所需的最少操作次数。

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$.

每个测试包含多个测试用例。

第一行包含一个整数 $t$（$1 \leq t \leq 10^3$）—— 测试用例的数量。随后是各测试用例的描述。

对于每个测试用例，第一行包含一个整数 $n$（$1 \leq n\leq 2\cdot 10^5$）—— 初始令牌数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_i \leq 10^9$）—— $n$ 个令牌的初始魔法值。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

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.

对于每个测试用例，输出一个整数——Patchouli 使所有符文的魔力值变为奇数所需的最少操作次数。

可以证明，在给定限制条件下，所需的这一操作序列一定存在。

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$.

测试用例 1：

$a$ 初始时仅由奇数组成。

测试用例 2：

选择魔法值为 $1$ 和 $2$ 的令牌并执行融合操作。此时 $a=[1,3]$，两个数均为奇数。

测试用例 3：

选择魔法值为 $2$ 和 $8$ 的令牌并执行融合操作。此时 $a=[4,10]$。

选择魔法值为 $10$ 的令牌并执行化简操作。此时 $a=[4,5]$。

选择魔法值为 $4$ 和 $5$ 的令牌并执行融合操作。此时 $a=[9]$，而 $9$ 是一个奇数。

可以证明，无法用少于 $3$ 步操作使所有魔法值变为奇数，因此答案为 $3$。