← 返回题目列表

Codeforces · 1688/B

B. 广藿香的神奇护身符

中文机器翻译题面 查看原题

广藿香正在制作一个神奇的护身符。她最初拥有 $$$n$$$ 魔法代币。他们的魔力可以用正整数$$$a_1, a_2, \ldots, a_n$$$来表示。

Patchouli 可以对令牌执行以下两个操作。

- 融合:广藿香选择两个令牌,将其移除,并创建一个新的令牌,其魔力等于两个所选令牌的总和。
- 缩减:广藿香选择一个魔力值为偶数 $$$x$$$ 的令牌,将其移除并创建一个魔力值等于 $$$\frac{x}{2}$$$ 的新令牌。

令牌的魔力为奇数时更有效。请帮助帕秋莉求出使所有令牌的魔力都为奇数所需的最少运算次数。

输入

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

第一行包含一个整数 $$$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$$$。

输出

对于每个测试用例,打印一个整数 - Patchouli 需要使所有令牌具有奇数魔力值的最小操作数。

可以证明,在这种限制下,存在所需的操作序列。

示例

输入 #1

4
2
1 9
3
1 1 2
3
2 4 8
3
1049600 33792 1280

输出 #1

0
1
3
10

注意

测试用例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$$$。