聪明的张博士有一个由n个整数a1,a2，…，an构成的数组a。他可以执行下列操作任意次:

（1) 从数组a中任选两项：ai和aj，其中ai的值必须是2的倍数

（2）ai = ai/2，即使得ai为原值的一半

（3）aj = aj*2，即使得aj为原值的两倍

张博士可以通过执行上面描述的操作任意次得到一个新的数组序列，显然元素的个数不变。请帮助张博士找到数组元素的最大和并输出。

第一行一个整数t：测试用例的数量(1≤t≤10⁴)。

每个测试用例共两行：

第一行包含一个整数n(1≤n≤15)，即数组中的元素个数。

第二行包含n个整数a1,a2，…，an(1≤ai<16)，即数组元素的值。

对于第一个测试用例[6, 4, 2]，最优操作序列如下：

（1）令i=2, j=1，则执行操作a2=4/2=2, a1=6*2=12，则得到新的序列[12, 2, 2]；

（2）令i=2, j=1，则执行操作a2=2/2=1, a1=12*2=24，则得到新的序列[24, 1, 2]；

（3）令i=3, j=1，则执行操作a3=2/2=1, a1=12*2=48，则得到新的序列[48, 1, 1]；

则最大和值为：48+1+1=50