广藿香正在制作一个神奇的护身符。她最初拥有 $$$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$$$。