在探索互联网的深处时,花栗鼠西奥多发现了一个非常有趣的正整数序列,并决定玩一下它。
在一次操作中,他选择序列的一个元素并执行以下操作:
- 如果所选元素是偶数,他将其除以 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 需要使序列中的所有数字相等的最小操作数。
示例
输入复制
533 2 473 6 7 16 8 8 731 4 2510 10 10 10 1061 1 3 1 1 1
输出复制
311203
注意
在第一个测试用例中,我们有一个序列:$$$[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$$$。