Patchouli's Magical Talisman

题意翻译

**题目描述** > 她擅长多种魔法，而且致力于开发新魔法。——《东方求闻史纪》 帕秋莉正在制作一个魔法护身符。她现在有 $n$ 个魔法令牌，令牌上的魔力值可以用正整数数列 $a_1,a_2,\dots,a_n$ 来表示。 帕秋莉可以对她的魔法令牌进行如下两种操作。 - 融合：帕秋莉可以选择两块令牌并且将它们移除，并且创造出一块新的令牌，其魔力值为这两块令牌的魔力值的和。 - 降低：帕秋莉可以选择一个魔力值为一个偶数 $x$ 的令牌，将其移除，创造出一块新的令牌，其魔力值变为 $\dfrac{x}{2}$。 由于当魔力值为奇数的时候这些令牌的工作效率会达到最高，所以请你帮助帕秋莉，告诉她把这些令牌的魔力值都变成奇数，所需的最小次数是多少。 **输入格式** 第一行输入一个正整数 $t(1 \leq t \leq 10^3)$，表示输入数据组数。 对于每组数据，第一行输入一个正整数 $n(1 \leq n \leq 2\times 10^5)$，表示魔法令牌的个数。 第二行输入 $n$ 个正整数 $a_i(1 \leq a_i \leq 10^9)$，表示魔法令牌上的魔力值。 数据保证，对于每组数据，$\sum n \leq 2 \times 10^5$。 **输出格式** 对于每一组数据，输出一个正整数，表示把这些令牌的魔力值都变成奇数，所需的最小次数是多少。可以证明一定存在一种方式。

题目描述

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.

输入输出格式

输入格式

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

输出格式

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.

输入输出样例

输入样例 #1

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

输出样例 #1

0
1
3
10

说明

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

题意翻译

**题目描述** > 她擅长多种魔法，而且致力于开发新魔法。——《东方求闻史纪》 帕秋莉正在制作一个魔法护身符。她现在有 $n$ 个魔法令牌，令牌上的魔力值可以用正整数数列 $a_1,a_2,\dots,a_n$ 来表示。 帕秋莉可以对她的魔法令牌进行如下两种操作。 - 融合：帕秋莉可以选择两块令牌并且将它们移除，并且创造出一块新的令牌，其魔力值为这两块令牌的魔力值的和。 - 降低：帕秋莉可以选择一个魔力值为一个偶数 $x$ 的令牌，将其移除，创造出一块新的令牌，其魔力值变为 $\dfrac{x}{2}$。 由于当魔力值为奇数的时候这些令牌的工作效率会达到最高，所以请你帮助帕秋莉，告诉她把这些令牌的魔力值都变成奇数，所需的最小次数是多少。 **输入格式** 第一行输入一个正整数 $t(1 \leq t \leq 10^3)$，表示输入数据组数。 对于每组数据，第一行输入一个正整数 $n(1 \leq n \leq 2\times 10^5)$，表示魔法令牌的个数。 第二行输入 $n$ 个正整数 $a_i(1 \leq a_i \leq 10^9)$，表示魔法令牌上的魔力值。 数据保证，对于每组数据，$\sum n \leq 2 \times 10^5$。 **输出格式** 对于每一组数据，输出一个正整数，表示把这些令牌的魔力值都变成奇数，所需的最小次数是多少。可以证明一定存在一种方式。