题目描述

William 有一个包含 $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$。

请你帮助 William 求出通过上述操作序列后，数组元素和的最大值。

输入格式

每组测试数据包含多组测试用例。第一行包含测试用例的数量 $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 < 16$），表示 William 的数组内容。

输出格式

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

说明/提示

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

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$。

由 ChatGPT 4.1 翻译

样例

5
3
6 4 2
5
1 2 3 4 5
1
10
3
2 3 4
15
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8

50
46
10
26
35184372088846