题目描述

在最后一次出击之前，Chtholly向Willem提出了三个问题。

第一个问题是：倘若结局无可避免，还需要多久才会一切归于虚无？

Willem无法直接回答她。于是他写下 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

每一次操作耗费一秒钟。在一次操作中，Willem完成如下步骤：

• 选定一个下标 $p$（$1\le p\le n$）；
• 将 $a_p$ 修改为 $\left\lfloor\dfrac{a_p}{2}\right\rfloor$；对于所有 $i\neq p$，将 $a_i$ 修改为 $\left\lceil\dfrac{a_i}{2}\right\rceil$。所有数值的修改同时进行。

求出使得全部 $n$ 个整数都变为 $0$ 所需要的最少秒数。

输入

每组数据包含多组测试用例。第一行输入测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各组测试用例。

每组测试用例第一行输入一个整数 $n$（$1\le n\le2\cdot10^5$），代表整数的个数。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le10^9$），代表初始的各个整数。

保证所有测试用例的 $n$ 之和不超过 $2\cdot10^5$。

输出

对每组测试用例，输出一个整数，即让所有整数全部变为 $0$ 需要的最少秒数。

样例

5
1
3
3
1 1 1
3
1 2 4
2
5 2
6
1 2 3 4 5 6

2
3
3
3
6

说明

第一组测试用例中，唯一数字变化过程为 $3\to1\to0$，因此答案为 $2$。

第二组测试用例中，值为 $1$ 的数只有选中它对应的下标时才会变成 $0$。因此至少需要 $3$ 秒，每个下标各选一次即可完成。

第三组测试用例的最优操作序列：

1. 选择 \(p=1\)：$[1,2,4]\to[0,1,2]$；
2. 选择 \(p=2\)：$[0,1,2]\to[0,0,1]$；
3. 选择 \(p=3\)：$[0,0,1]\to[0,0,0]$。

第四组测试用例的最优变换过程 $[5,2]\to[2,1]\to[1,0]\to[0,0]$，依次选择下标 $1$、$2$、$1$。

原题链接

原题链接