← 返回题目列表

Codeforces · 1277/B

B. 让他们变得奇怪

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

有 $$$n$$$ 正整数 $$$a_1, a_2, \dots, a_n$$$。对于一步棋,您可以选择任何偶​​数 $$$c$$$ 并将等于 $$$c$$$ 的所有元素除以两个。

例如,如果$$$a=[6,8,12,6,3,12]$$$并且您选择$$$c=6$$$,则移动后$$$a$$$将转换为$$$a=[3,8,12,3,3,12]$$$。

您需要找到将 $$$a$$$ 转换为仅包含奇数整数的数组(每个元素不应被 $$$2$$$ 整除)的最小移动次数。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含 $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — 序列 $$$a$$$ 中整数的数量。第二行包含正整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

输入中所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。

输出

对于 $$$t$$$ 测试用例,按照输入中测试用例的顺序打印答案。测试用例的答案是使测试用例中的所有数字都为奇数所需的最少移动次数(即不能被 $$$2$$$ 整除)。

示例

输入 #1

4
6
40 6 40 3 20 1
1
1024
4
2 4 8 16
3
3 1 7

输出 #1

4
10
4
0

注意

在示例的第一个测试用例中,最佳移动顺序如下:

- 移动之前 $$$a=[40, 6, 40, 3, 20, 1]$$$;
- 选择$$$c=6$$$;
- 现在 $$$a=[40, 3, 40, 3, 20, 1]$$$;
- 选择$$$c=40$$$;
- 现在 $$$a=[20, 3, 20, 3, 20, 1]$$$;
- 选择$$$c=20$$$;
- 现在 $$$a=[10, 3, 10, 3, 10, 1]$$$;
- 选择$$$c=10$$$;
- 现在 $$$a=[5, 3, 5, 3, 5, 1]$$$ - 所有数字都是奇数。

因此,$$$4$$$ 移动后所有数字都变成奇数。在 $$$3$$$ 或更少的移动中,你不能让它们都是奇数。