CF2255D.How Long Until Nothing Remains?

Before her final sortie, Chtholly asks Willem three questions.

The first is this: if the end is inevitable, how long will it take until nothing remains?

Willem cannot answer her directly. Instead, he writes down $n$ positive integers $a_1,a_2,\ldots,a_n$.

Each operation takes one second. In one operation, Willem does the following:

• Choose an index $p$ ($1\le p\le n$);
• Then, replace $a_p$ with $\left\lfloor\dfrac{a_p}{2}\right\rfloor$, and for every $i\ne p$, replace $a_i$ by $\left\lceil\dfrac{a_i}{2}\right\rceil$. All replacements are performed simultaneously.

Find the minimum number of seconds needed to make all $n$ integers equal to $0$.

在她最后一次出击之前，克洛伊向威尔姆提出了三个问题。

第一个问题是：如果终结不可避免，那么需要多长时间才会什么都不剩？

威尔姆无法直接回答她。相反，他写下了 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

每次操作耗时一秒。在一次操作中，威尔姆执行以下步骤：

• 选择一个下标 $p$（满足 $1\le p\le n$）；
• 然后将 $a_p$ 替换为 $\left\lfloor\dfrac{a_p}{2}\right\rfloor$，并对每个 $i\ne p$，将 $a_i$ 替换为 $\left\lceil\dfrac{a_i}{2}\right\rceil$。所有替换同时进行。

求使全部 $n$ 个整数均变为 $0$ 所需的最少秒数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1\le n\le2\cdot10^5$) — the number of integers.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le10^9$) — the initial integers.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output a single integer — the minimum number of seconds needed to make all integers equal to $0$.

对于每个测试用例，输出一个整数——使所有整数变为 $0$ 所需的最少秒数。

In the first test case, the only integer changes as $3\to1\to0$, so the answer is $2$.

In the second test case, an integer equal to $1$ becomes $0$ only when its index is chosen. Thus, at least $3$ seconds are necessary, and choosing every index once is sufficient.

In the third test case, an optimal sequence is:

1. Choose $p=1$: $[1,2,4]\to[0,1,2]$;
2. Choose $p=2$: $[0,1,2]\to[0,0,1]$;
3. Choose $p=3$: $[0,0,1]\to[0,0,0]$.

In the fourth test case, an optimal sequence is $[5,2]\to[2,1]\to[1,0]\to[0,0]$, where the chosen indices are $1$, $2$, and $1$.

在第一个测试用例中，唯一的整数变化过程为 $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$。