CF1609A.Divide and Multiply

William has array of $n$ numbers $a_1, a_2, \dots, a_n$. He can perform the following sequence of operations any number of times:

1. Pick any two items from array $a_i$ and $a_j$, where $a_i$ must be a multiple of $2$
2. $a_i = \frac{a_i}{2}$
3. $a_j = a_j \cdot 2$

Help William find the maximal sum of array elements, which he can get by performing the sequence of operations described above.

威廉有一个包含 $n$ 个数的数组 $a_1, a_2, \dots, a_n$。他可以任意多次执行以下操作序列：

1. 从数组中任选两个元素 $a_i$ 和 $a_j$，其中 $a_i$ 必须是 $2$ 的倍数；
2. 将 $a_i$ 替换为 $\frac{a_i}{2}$；
3. 将 $a_j$ 替换为 $a_j \cdot 2$。

请帮助威廉求出通过执行上述操作所能得到的数组元素之和的最大值。

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

The first line of each test case contains an integer $n$ $(1 \le n \le 15)$, the number of elements in William's array.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \lt 16)$, the contents of William's array.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 15$），表示 William 数组中的元素个数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \lt 16$），即 William 数组的内容。

For each test case output the maximal sum of array elements after performing an optimal sequence of operations.

对于每个测试用例，输出执行最优操作序列后数组元素的最大和。

In the first example test case the optimal sequence would be:

1. Pick $i = 2$ and $j = 1$. After performing a sequence of operations $a_2 = \frac{4}{2} = 2$ and $a_1 = 6 \cdot 2 = 12$, making the array look as: [12, 2, 2].
2. Pick $i = 2$ and $j = 1$. After performing a sequence of operations $a_2 = \frac{2}{2} = 1$ and $a_1 = 12 \cdot 2 = 24$, making the array look as: [24, 1, 2].
3. Pick $i = 3$ and $j = 1$. After performing a sequence of operations $a_3 = \frac{2}{2} = 1$ and $a_1 = 24 \cdot 2 = 48$, making the array look as: [48, 1, 1].

The final answer $48 + 1 + 1 = 50$.

In the third example test case there is no way to change the sum of elements, so the answer is $10$.

在第一个样例测试用例中，最优操作序列为：

1. 选择 $i = 2$ 和 $j = 1$。执行一系列操作后，$a_2 = \frac{4}{2} = 2$，$a_1 = 6 \cdot 2 = 12$，数组变为：[12, 2, 2]。
2. 选择 $i = 2$ 和 $j = 1$。执行一系列操作后，$a_2 = \frac{2}{2} = 1$，$a_1 = 12 \cdot 2 = 24$，数组变为：[24, 1, 2]。
3. 选择 $i = 3$ 和 $j = 1$。执行一系列操作后，$a_3 = \frac{2}{2} = 1$，$a_1 = 24 \cdot 2 = 48$，数组变为：[48, 1, 1]。

最终答案为 $48 + 1 + 1 = 50$。

在第三个样例测试用例中，无法改变元素之和，因此答案为 $10$。