CF2246D.diss_quack and Array Game

You are given an array $a$ of $n$ integers. Alice and Bob will play a game with this array.

Before the game with Bob starts, Alice can increment any element of the array any number of times, each increment taking one move. One increment consists of a single addition by $1$ to one index.

After that, the game starts and Bob and Alice take turns, with Bob making the first move. On Bob's turn, he can choose any two indices $i$ and $j$ and swap the array elements at these indices (note that Bob may choose $i = j$, in which case the array remains unchanged after the swap).

On Alice's turn, if $a_1$ is even, she finds the largest $j \leq |a|$ such that $a_i$ is even for all $i \leq j,$ then sets $a_i := a_i/2$ for $i \leq j.$ Otherwise she sets $a_1 := a_1 - 1.$ If any element becomes zero, it automatically gets erased from the array (and the other elements are re-indexed accordingly).

The game ends when the array is empty.

Alice wants to minimize the number of moves she makes, while Bob wants to maximize the number of moves Alice makes. Note that the number of moves is the sum of the number of initial additions and the number of turns Alice plays after.

How many moves will Alice make with optimal play?

给你一个包含 $n$ 个整数的数组 $a$。Alice 和 Bob 将用该数组进行一场游戏。

在与 Bob 的游戏开始之前，Alice 可以对数组中的任意元素执行任意多次“增量”操作，每次增量操作算作一步。一次增量操作即对某个下标处的元素加 $1$。

之后，游戏正式开始，Bob 和 Alice 轮流行动，Bob 先手。在 Bob 的回合中，他可以任选两个下标 $i$ 和 $j$，并交换这两个位置上的数组元素（注意：Bob 允许选择 $i = j$，此时数组保持不变）。

在 Alice 的回合中，若 $a_1$ 是偶数，则她找出最大的 $j \leq |a|$，使得对所有 $i \leq j$ 都有 $a_i$ 为偶数，然后对所有 $i \leq j$ 执行 $a_i := a_i/2$；否则（即 $a_1$ 为奇数），她执行 $a_1 := a_1 - 1$。若某个元素变为零，则该元素自动从数组中删除（其余元素相应地重新编号）。

当数组变为空时，游戏结束。

Alice 希望最小化她所执行的总步数，而 Bob 则希望最大化 Alice 的总步数。注意：总步数等于初始增量操作的次数加上游戏开始后 Alice 实际参与的回合数。

在双方均采取最优策略的情况下，Alice 总共将执行多少步？

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 a single integer $n \, (1 \le n \le 10^5)$ — the length of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_{n}\,(1 \le a_i \le 10^5)$ — the elements of the array.

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $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^5$）—— 数组的元素。

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

For each test case, output a single integer — the number of moves Alice will make if both players play optimally.

对于每个测试用例，输出一个整数——即在双方都采取最优策略的情况下，Alice 将进行的移动次数。

In the first case, Alice chooses not to add to any element initially. On the first move, Bob chooses $i = j = 1$ (not swapping any elements). Then Alice subtracts $1$ from $a_1,$ making the array $[2,3]$. Next, Bob again chooses $i = j = 1.$ Alice divides $a_1$ by $2$, and the array becomes $[1,3]$. Bob again chooses $i = j = 1.$ Alice subtracts from $a_1,$ and the array becomes $[3]$. Bob must now choose $i = j = 1,$ and Alice takes $3$ more moves to make the array empty. In total, Alice takes $6$ moves. It can be shown that this is the result of optimal play.

In the second test case, Alice again chooses not to add to any element initially. It can be shown that with optimal play, Alice takes $5$ moves.

在第一种情况下，Alice 初始时选择不对任何元素进行加法操作。在第一步中，Bob 选择 $i = j = 1$（即不交换任何元素）。接着 Alice 将 $a_1$ 减去 $1$，使数组变为 $[2,3]$。随后 Bob 再次选择 $i = j = 1$；Alice 将 $a_1$ 除以 $2$，数组变为 $[1,3]$。Bob 再次选择 $i = j = 1$；Alice 对 $a_1$ 进行减法操作，数组变为 $[3]$。此时 Bob 必须再次选择 $i = j = 1$，而 Alice 还需额外 $3$ 步才能使数组变为空。总计，Alice 共进行了 $6$ 步操作。可以证明，这是双方均采取最优策略时的结果。

在第二个测试用例中，Alice 同样初始时选择不对任何元素进行加法操作。可以证明，在双方均采取最优策略的情况下，Alice 共需 $5$ 步操作。