← 返回题目列表

Codeforces · 2231/C

C. 花栗鼠理论和平等

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

在探索互联网的深处时,花栗鼠西奥多发现了一个非常有趣的正整数序列,并决定玩一下它。

在一次操作中,他选择序列的一个元素并执行以下操作:

  • 如果所选元素是偶数,他将其除以 2。
  • 如果选择的元素是奇数,他将其加 1。

Theo 非常喜欢平等,所以他想让序列中的所有数字都相等(否则,某些数字可能会感到被冒犯)。由于他需要计划午餐时间,请帮助他确定使所有数字相等所需的最少运算次数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 序列的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 序列的元素。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,输出一个整数 - Theo 需要使序列中的所有数字相等的最小操作数。

示例

输入
复制

5
3
3 2 4
7
3 6 7 16 8 8 7
3
1 4 2
5
10 10 10 10 10
6
1 1 3 1 1 1

输出
复制

3
11
2
0
3

注意

在第一个测试用例中,我们有一个序列:$$$[3, 2, 4]$$$

一种可能的操作序列: $$[\textbf{3}, 2, 4] \rightarrow [\textbf{4}, 2, 4] \rightarrow [2, 2, \textbf{4}] \rightarrow [2, 2, 2]$$ (对粗体显示的数字执行操作。)

在第二个测试用例中,序列为:$$$[3, 6, 7, 16, 8, 8, 7]$$$

可能的操作:

  • 对第一个元素执行一次操作:$$$3 \rightarrow 4$$$
  • 对第二个元素执行两次操作:$$$6 \rightarrow 3 \rightarrow 4$$$
  • 对第 4 个元素执行两次操作:$$$7 \rightarrow 8 \rightarrow 4$$$
  • 对第 5 个元素执行两次操作:$$$16 \rightarrow 8 \rightarrow 4$$$
  • 对第 6 个元素执行一次操作:$$$8 \rightarrow 4$$$
  • 对第 7 个元素执行一次操作:$$$8 \rightarrow 4$$$
  • 对第 8 个元素执行两次操作:$$$7 \rightarrow 8 \rightarrow 4$$$

经过这些 $$$11$$$ 操作,所有元素都变成 $$$4$$$。