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, \ldots, a_n $。她可以通过两种操作来改变令牌的魔力值：融合和降低。融合操作是指选择两个令牌，将它们移除并创造一个新令牌，其魔力值为这两个令牌的魔力值之和；降低操作是指选择一个魔力值为偶数的令牌，将其移除并创造一个新令牌，其魔力值为此令牌魔力值的一半。帕秋莉的目标是通过这些操作使得所有令牌的魔力值都变为奇数。需要求出达到目标所需的最小操作次数。

**输入格式：**
第一行输入一个正整数 $ t $，表示测试用例的数量。每个测试用例包含两行，第一行输入一个正整数 $ n $，表示魔法令牌的数量。第二行输入 $ n $ 个正整数 $ a_i $，表示每个令牌的初始魔力值。

**输出格式：**
对于每个测试用例，输出一个正整数，表示将所有令牌的魔力值变为奇数所需的最小操作次数。

**输入输出样例：**
**输入样例 #1：**
```
4
2
1 9
3
1 1 2
3
2 4 8
3
1049600 33792 1280
```
**输出样例 #1：**
```
0
1
3
10
```

**说明：**
- 在第一个测试用例中，所有令牌的魔力值已经是奇数，所以不需要任何操作。
- 在第二个测试用例中，可以通过融合两个值为1的令牌来得到一个值为2的令牌，然后执行降低操作得到一个值为1的令牌，因此总共需要1次操作。
- 在第三个测试用例中，可以通过融合一个值为2和一个值为8的令牌得到一个值为10的令牌，然后执行降低操作得到一个值为5的令牌，最后融合一个值为4和一个值为5的令牌得到一个值为9的令牌，因此总共需要3次操作。
- 在第四个测试用例中，可以通过一系列操作得到所有令牌的魔力值都为奇数，总共需要10次操作。**题目大意：** 帕秋莉正在制作一个魔法护身符，她有 $ n $ 个魔法令牌，每个令牌都有一个正整数的魔力值 $ a_1, a_2, \ldots, a_n $。她可以通过两种操作来改变令牌的魔力值：融合和降低。融合操作是指选择两个令牌，将它们移除并创造一个新令牌，其魔力值为这两个令牌的魔力值之和；降低操作是指选择一个魔力值为偶数的令牌，将其移除并创造一个新令牌，其魔力值为此令牌魔力值的一半。帕秋莉的目标是通过这些操作使得所有令牌的魔力值都变为奇数。需要求出达到目标所需的最小操作次数。 **输入格式：** 第一行输入一个正整数 $ t $，表示测试用例的数量。每个测试用例包含两行，第一行输入一个正整数 $ n $，表示魔法令牌的数量。第二行输入 $ n $ 个正整数 $ a_i $，表示每个令牌的初始魔力值。 **输出格式：** 对于每个测试用例，输出一个正整数，表示将所有令牌的魔力值变为奇数所需的最小操作次数。 **输入输出样例：** **输入样例 #1：** ``` 4 2 1 9 3 1 1 2 3 2 4 8 3 1049600 33792 1280 ``` **输出样例 #1：** ``` 0 1 3 10 ``` **说明：** - 在第一个测试用例中，所有令牌的魔力值已经是奇数，所以不需要任何操作。 - 在第二个测试用例中，可以通过融合两个值为1的令牌来得到一个值为2的令牌，然后执行降低操作得到一个值为1的令牌，因此总共需要1次操作。 - 在第三个测试用例中，可以通过融合一个值为2和一个值为8的令牌得到一个值为10的令牌，然后执行降低操作得到一个值为5的令牌，最后融合一个值为4和一个值为5的令牌得到一个值为9的令牌，因此总共需要3次操作。 - 在第四个测试用例中，可以通过一系列操作得到所有令牌的魔力值都为奇数，总共需要10次操作。