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
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
输出 #1
50 46 10 26 35184372088846
注意
在第一个示例测试用例中,最佳序列是:
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$$$。