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:

Pick any two items from array $a_i$ and $a_j$, where $a_i$ must be a multiple of $2$

$a_i = \frac{a_i}{2}$

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


-----Input-----

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 < 16)$, the contents of William's array.


-----Output-----

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


-----Examples-----

Input
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
Output
50
46
10
26
35184372088846


-----Note-----

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

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].

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].

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

Difficulty: EASY
Tags: Mathematics

Number theory

Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	x = 1
	for i in range(n):
		while a[i] % 2 == 0:
			a[i] //= 2
			x *= 2
	a.sort()
	a[-1] *= x
	print(sum(a))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


for s in [*open(0)][2::2]:
	(*a,) = map(int, s.split())
	i = 0
	k = 1
	for x in a:
		x &= -x
		a[i] //= x
		k *= x
		i += 1
	print(sum(a) + max(a) * (k - 1))


w = int(input())
l = []
sum = 0
power = 0
for i in range(w):
	k = int(input())
	t = list(map(int, input().split()))
	l.append(t)

def count2(n):
	maxn = 0
	power = 0
	sum = 0
	for i in n:
		while i % 2 == 0:
			power += 1
			i = i // 2
		sum += i
		if maxn < i:
			maxn = i
	return (sum, power, maxn)
for i in l:
	q = count2(i)
	print(q[0] - q[2] + q[2] * 2 ** q[1])


def f(a):
	k = j = 0
	while j < len(a):
		if not a[j] % 2:
			a[j] //= 2
			k += 1
		else:
			j += 1
	a.sort()
	a[-1] *= 2 ** k
	return sum(a)
t = int(input())
c = []
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c.append(f(a))
for _ in c:
	print(_)


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	arr = [int(x) for x in sys.stdin.readline().split()]
	mul = 1
	for i in range(len(arr)):
		while arr[i] % 2 == 0:
			arr[i] //= 2
			mul *= 2
	arr.sort()
	arr[-1] *= mul
	print(sum(arr))


from sys import stdin
t = int(stdin.readline())
while t > 0:
	t -= 1
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	p = 1
	for i in range(n):
		while a[i] % 2 == 0:
			p *= 2
			a[i] //= 2
	M = max(a)
	print(sum(a) - M + M * p)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().strip().split()))
	c = 0
	for i in range(n):
		while a[i] % 2 == 0:
			c += 1
			a[i] //= 2
	print(2 ** c * max(a) + (sum(a) - max(a)))


import sys
k = int(sys.stdin.readline())
for i in range(k):
	n = int(sys.stdin.readline())
	js = list(map(int, sys.stdin.readline().strip().split(' ')))
	rs = 1
	for j in range(len(js)):
		while js[j] % 2 == 0:
			js[j] //= 2
			rs *= 2
	js.sort()
	print(sum(js[:-1]) + rs * js[-1])


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
for _ in range(int(input())):
	n = int(input())
	a = inp()
	c = 0
	for i in range(n):
		while a[i] % 2 == 0:
			a[i] //= 2
			c += 1
	a.sort()
	a[-1] *= 2 ** c
	print(sum(a))


for s in [*open(0)][2::2]:
	(*a,) = map(int, s.split())
	m = k = max((b := [x // (x & -x) for x in a]))
	for (x, y) in zip(a, b):
		m *= x // y
	print(sum(b) - k + m)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	input()
	w = list(map(int, input().split()))
	(c, d) = (0, [])
	for i in w:
		while i % 2 == 0:
			i //= 2
			c += 1
		d.append(i)
	d.sort()
	print(sum(d[:-1]) + d[-1] * 2 ** c)


import sys

def v2(x):
	v = 0
	while x % 2 == 0:
		x //= 2
		v += 1
	return (v, x)

def main():
	input = sys.stdin.readline
	nbT = int(input())
	for i in range(nbT):
		n = int(input())
		a = list(map(int, input().split()))
		b = []
		s = 0
		for x in a:
			(v, y) = v2(x)
			s += v
			b.append(y)
		print(sum(b) - max(b) + max(b) * 2 ** s)
main()


from collections import Counter
from math import ceil, floor, log
import bisect as bs
import sys
input = sys.stdin.readline
inp_lis = lambda : list(map(int, input().split()))
inp_multi = lambda : map(int, input().split())
inp_int = lambda : int(input().strip())
for _ in range(int(input())):
	n = inp_int()
	a = inp_lis()
	c = 0
	for i in range(n):
		while a[i] % 2 == 0:
			c += 1
			a[i] = a[i] // 2
	print(sum(a) - max(a) + max(a) * 2 ** c)


import sys
import bisect
import math
from collections import deque
input = lambda : sys.stdin.readline().strip()
mod = 10 ** 9 + 7

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	(max_odd, even, s) = (1, 1, 0)
	for i in range(n):
		x = a[i]
		while x % 2 == 0:
			x //= 2
			even *= 2
		max_odd = max(max_odd, x)
		s += x
	return max_odd * even + s - max_odd
t = 1
t = int(input())
for _ in range(t):
	print(solve())


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	ai = list(map(int, input().split()))
	val = 0
	for i in range(n):
		while ai[i] % 2 == 0:
			ai[i] //= 2
			val += 1
	ai[ai.index(max(ai))] *= pow(2, val)
	print(sum(ai))


import sys

def powerOfTwo(n):
	power = 0
	while n % 2 == 0:
		power += 1
		n = n // 2
	return power

def main():
	input = sys.stdin.readline
	print = sys.stdout.write
	t = int(input())
	for i in [0] * t:
		n = int(input())
		nums = list(map(int, input().split()))
		power_of_two = 0
		for k in range(n):
			p_t = powerOfTwo(nums[k])
			power_of_two += p_t
			nums[k] = nums[k] // 2 ** p_t
		max_num = max(nums)
		answer = sum(nums) + max_num * 2 ** power_of_two - max_num
		print(str(answer) + '\n')
main()


t = int(input())

def dic(arr):
	d = {}
	no = 0
	lol = 0
	sub = 0
	mx = 1
	for i in arr:
		count = 0
		if True:
			x = i
			while i % 2 == 0:
				i = i // 2
				count += 1
				no += 1
			lol += i
			if i > mx:
				mx = i
	ans = mx * 2 ** no + lol - mx
	return ans
while t > 0:
	t = t - 1
	n = int(input())
	arr = list(map(int, input().split()))
	if n != 1:
		print(int(dic(arr)))
	else:
		print(int(*arr))


def get_min2(list):
	for min in list:
		if min % 2 == 0:
			break
		else:
			continue
	for item in list:
		if item < min and item % 2 == 0:
			min = item
		else:
			continue
	return min

def chu2(n):
	i = 0
	while n % 2 == 0:
		n = n / 2
		i += 1
	return (n, i)

def operation(num, list):
	nsum = 0
	sum1 = 0
	for i in range(0, num):
		if list[i] % 2 != 0:
			continue
		else:
			(list[i], b) = chu2(list[i])
			nsum += b
	max1 = max(list)
	index_max = list.index(max1)
	list[index_max] = max1 * 2 ** nsum
	sum1 = sum(list)
	return sum1
while True:
	try:
		answer = []
		a = int(input())
		list1 = []
		for i in range(0, a):
			b = int(input())
			list1 = list(map(int, input().split()))
			c = len(list1)
			d = operation(c, list1)
			answer.append(d)
		for item in answer:
			print(int(item))
	except:
		break


t = int(input())
k = 0
lst = []
while t > 0:
	a = int(input())
	l = list(map(int, input().split()))
	for x in range(a):
		while l[x] % 2 == 0:
			l[x] = l[x] // 2
			k += 1
	l = sorted(l)
	for x in range(k):
		l[-1] *= 2
	k = 0
	lst.append(str(sum(l)))
	t -= 1
print('\n'.join(lst))


def solve():
	n = int(input())
	a = list(map(int, input().split(' ')))
	temp = 1
	for i in range(n):
		while a[i] % 2 == 0:
			a[i] //= 2
			temp *= 2
	a.sort()
	a[-1] *= temp
	print(sum(a))
t = int(input())
for i in range(t):
	solve()


import sys
import bisect
inp = sys.stdin.readline

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(inp())):
	n = int(inp())
	a = [int(i) for i in inp().split()]
	a.sort()
	c = 0
	for i in range(n):
		while a[i] % 2 == 0:
			c += 1
			a[i] //= 2
	print(sum(a) - max(a) + max(a) * 2 ** c)


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 1
	for i in range(n):
		while arr[i] % 2 == 0:
			arr[i] //= 2
			ans *= 2
	print(sum(arr) + max(arr) * ans - max(arr))
tst = int(input())
for i in range(tst):
	solve()


res = []
tests = int(input())
res.extend(range(0, tests))
for i in range(0, tests):
	size = int(input())
	arr = list(map(int, input().split()))
	n = 0
	for j in range(0, size):
		while arr[j] % 2 == 0:
			arr[j] = arr[j] / 2
			n = n + 1
		j = j + 1
	x = max(arr)
	arr.remove(x)
	arr.append(2 ** n * x)
	res[i] = int(sum(arr))
for i in range(0, tests):
	print(res[i])


from collections import Counter
import bisect as bs
import sys
input = sys.stdin.readline
from math import ceil, floor, log
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	y = 0
	for i in range(n):
		while a[i] % 2 == 0:
			y += 1
			a[i] = a[i] // 2
	print(sum(a) - max(a) + 2 ** y * max(a))


from collections import defaultdict as dd
import math
import sys
input = sys.stdin.readline

def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return map(int, input().split())

def lm():
	return list(map(int, input().split()))

def find_two(num):
	n = 0
	while num % 2 == 0:
		num /= 2
		n += 1
	return (n, num)

def main():
	num_cases = nn()
	for n in range(num_cases):
		num_elems = nn()
		elems = lm()
		total = 0
		twos = 0
		new_elems = [find_two(x) for x in elems]
		max_elem = new_elems[0]
		for e in new_elems:
			if e[1] > max_elem[1]:
				max_elem = e
			total += e[1]
			twos += e[0]
		total -= max_elem[1]
		total += max_elem[1] * 2 ** twos
		print(int(total))
main()


n = int(input())
p = []
a = []
for k in range(n):
	a.append(input())
	for i in range(len(a)):
		p.append(input().split())
	a = []
for i in range(len(p)):
	r = p[i]
	r = [int(i) for i in r]
	count = 0
	for k in range(len(r)):
		while r[k] % 2 == 0:
			count = count + 1
			r[k] = int(r[k] / 2)
	r.sort()
	r[-1] = r[-1] * 2 ** count
	print(sum(r))


import sys
import math
import copy
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def inltstr():
	return list(map(str, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def factorial(n):
	if n == 1:
		return n
	elif n < 1:
		return 'NA'
	else:
		return n * factorial(n - 1)

def coeffBin(k):
	return factorial(k + 1) / (factorial(2) * factorial(k - 1))

def solve(n, arr):
	res = 1
	c = []
	sub = []
	for i in arr:
		temp = 1
		while i % 2 == 0:
			temp = temp * 2
			i = i / 2
		sub.append(int(i))
		if temp > 0:
			c.append(temp)
	m = max(sub)
	ind = sub.index(m)
	res = arr[ind]
	arr.remove(res)
	sub.remove(m)
	c.remove(c[ind])
	for x in c:
		res = res * x
	for x in sub:
		res += x
	return res
res = []
iter = inp()
i = 0
while i < iter:
	n = inp()
	arr = inlt()
	result = solve(n, arr)
	res.append(result)
	i += 1
for r in res:
	print(r)


for s in [*open(0)][2::2]:
	(*a,) = map(int, s.split())
	i = (b := [x // (x & -x) for x in a]).index(max(b))
	j = 0
	for (x, y) in zip(a, b):
		a[i] *= x // y
		a[j] //= x // y
		j += 1
	print(sum(a))


import itertools
from math import floor, log, log2, ceil, sqrt
from itertools import groupby
from decimal import Decimal, getcontext
import sys
from collections import deque
t = int(input())
res = []
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	counts = 0
	_max = 0
	ans = 0
	for i in range(n):
		ost = 0
		if a[i] % 2 == 0:
			mult = 0
			ost = a[i]
			while ost % 2 == 0:
				mult += 1
				ost = ost // 2
			counts += mult
		else:
			ost = a[i]
		if ost > _max:
			_max = ost
		ans += ost
	ans = ans - _max + _max * 2 ** counts
	res.append(ans)
for i in range(t):
	print(res[i])


def p(num):
	k = 0
	while num % 2 != 1:
		k = k + 1
		num = num / 2
	return pow(2, k)

def f(n, l):
	c = 1
	a = -1
	id = -1
	for i in range(n):
		if l[i] % 2 == 0:
			f = p(l[i])
			c = c * f
			l[i] = l[i] // f
		if l[i] > a:
			a = l[i]
			id = i
	l[id] = l[id] * c
	return sum(l)
x = int(input())
m = []
for i in range(x):
	z = int(input())
	y = input()
	y1 = y.split(' ')
	y2 = [int(t) for t in y1]
	m.append((z, y2))
for j in range(x):
	print(f(m[j][0], m[j][1]))


def lol(arr, n):
	m = 1
	for i in range(n):
		while arr[i] % 2 == 0:
			m = m * 2
			arr[i] = arr[i] // 2
	arr.sort()
	arr[-1] = arr[-1] * m
	print(sum(arr))
	return
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	lol(arr, n)


t = int(input())

def check(x):
	if x % 2 != 0:
		return (0, x)
	elif x % 2 == 0 and x % 4 != 0:
		return (1, x // 2)
	elif x % 4 == 0 and x % 8 != 0:
		return (2, x // 4)
	elif x == 8:
		return (3, 1)
ans = []
for i in range(0, t):
	n = int(input())
	arr = list(map(int, input().split()))
	lastin = 0
	for j in range(0, n):
		(a, b) = check(arr[j])
		lastin += a
		arr[j] = b
	m = max(arr)
	arr.remove(m)
	alpha = sum(arr)
	alpha += 2 ** lastin * m
	ans.append(alpha)
for x in ans:
	print(x)


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	two = 0
	for i in range(n):
		while arr[i] % 2 == 0 and arr[i] != 0:
			two += 1
			arr[i] = arr[i] // 2
	mx = max(arr)
	m = mx * pow(2, two)
	return sum(arr) - mx + m
for _ in range(int(input())):
	print(main())


from sys import stdin
import math
from collections import deque
from heapq import heapify, heappop, heappush
from bisect import bisect_left, bisect_right
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(total, product, odd, oddidx) = (0, 1, True, 0)
	for i in range(n):
		a = arr[i]
		power = a & ~(a - 1)
		product *= power
		arr[i] //= power
		if arr[i] % 2 == 1:
			odd = True
			if arr[i] > arr[oddidx]:
				oddidx = i
	print(sum(arr) - arr[oddidx] + product * arr[oddidx])


t = int(input())
for _ in range(t):
	n = int(input())
	v = list(map(int, input().split()))
	k = 0
	b = []
	for x in v:
		while x % 2 == 0:
			x //= 2
			k += 1
		b.append(x)
	b.sort()
	b[-1] *= 1 << k
	print(sum(b))


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	sys.stderr = open('error.txt', 'w')
depth = 1000000
mod = 1000000007
lim = mod * mod
sys.setrecursionlimit(depth)
linp = lambda : list(minp())
minp = lambda : map(int, input().split())
from math import inf, ceil, sqrt, log2, gcd
from collections import defaultdict, deque
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def expo(a, b):
	if not b:
		return 1
	v = expo(a, b // 2)
	v = v * v % mod
	if b % 2:
		v = v * a % mod
	return v

def modinv(a, b):
	d = expo(b, mod - 2)
	v = a * d % mod
	return v

def checkPrime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	for i in range(3, int(sqrt(n)) + 1, 2):
		if n % i == 0:
			return False
	return True
for _ in range(int(input())):
	n = int(input())
	a = linp()
	v = 1
	for i in range(n):
		while a[i] % 2 == 0:
			a[i] = a[i] // 2
			v = v * 2
	a.sort()
	a[-1] *= v
	print(sum(a))


import sys
for _ in range(int(input())):
	n = list(map(int, sys.stdin.readline().split()))
	arr = list(map(int, sys.stdin.readline().split()))
	count = 0
	for i in range(len(arr)):
		x = (arr[i] & -arr[i]).bit_length() - 1
		arr[i] = arr[i] // 2 ** x
		count += x
	arr.sort()
	arr[-1] = arr[-1] * 2 ** count
	print(sum(arr))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = 0
	for i in range(n):
		while a[i] % 2 == 0:
			a[i] //= 2
			k += 1
	a.sort()
	a[-1] *= 2 ** k
	ans = sum(a)
	print(ans)


nadiri = int(input())
for _ in range(nadiri):
	lomi = int(input())
	andria = 0
	cotne = list(map(int, input().split()))
	for i in range(len(cotne)):
		while cotne[i] % 2 == 0:
			andria = andria + 1
			cotne[i] //= 2
	print(sum(cotne) + max(cotne) * (2 ** andria - 1))


def solve():
	input()
	array_map = map(int, input().split())
	(even, odd) = ([], [])
	k = 0
	for element in array_map:
		if element % 2:
			odd.append(element)
		else:
			even.append(element)
	while even:
		num = even.pop()
		while not num % 2:
			k += 1
			num //= 2
		odd.append(num)
	highest = max(odd)
	print(highest * 2 ** k + sum(odd) - highest)
for _ in range(int(input())):
	solve()


def divideMultipy(arr, n):
	temp = 1
	for i in range(n):
		while arr[i] % 2 == 0:
			arr[i] = arr[i] // 2
			temp *= 2
	arr.sort()
	arr[-1] *= temp
	return sum(arr)
testcase = int(input())
while testcase != 0:
	testcase -= 1
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(divideMultipy(arr, n))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	tmp = 1
	for i in range(n):
		while a[i] % 2 == 0:
			tmp *= 2
			a[i] //= 2
	a = sorted(a)
	print(sum(a[:-1]) + a[-1] * tmp)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	tp = 0
	for i in range(n):
		while a[i] % 2 == 0:
			a[i] = a[i] // 2
			tp = tp + 1
	su = sum(a) - max(a) + max(a) * 2 ** tp
	print(su)


def f(l):
	x = 0
	for i in range(len(l)):
		while l[i] % 2 == 0:
			l[i] = l[i] // 2
			x = x + 1
	return sum(l) - max(l) + 2 ** x * max(l)
n = int(input())
for _ in range(n):
	t = int(input())
	l = list(map(int, input().split()))
	print(f(l))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	x = 0
	y = n - 1
	var = 0
	for j in range(y + 1):
		while l[j] % 2 == 0:
			l[j] = l[j] // 2
			var += 1
	l.sort()
	l[y] = l[y] * 2 ** var
	print(sum(l))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = 1
	for i in range(n):
		while l[i] % 2 == 0:
			a *= 2
			l[i] //= 2
	l.sort()
	l[-1] *= a
	print(sum(l))


def dnm():
	n = int(input())
	a = list(map(int, input().split()))
	te = 1
	for i in range(n):
		while a[i] % 2 == 0:
			a[i] = a[i] // 2
			te = te * 2
	a.sort()
	a[-1] = a[-1] * te
	print(sum(a))
t = int(input())
for i in range(t):
	dnm()


for _ in range(0, int(input())):
	n = int(input())
	v = list(map(int, input().split()))
	t = 0
	for (i, x) in enumerate(v):
		while x % 2 == 0:
			x //= 2
			t += 1
		v[i] = x
	(*u, M) = sorted(v)
	print(M * 2 ** t + sum(u))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	for i in range(n):
		while arr[i] % 2 == 0:
			arr[i] //= 2
			count += 1
	arr.sort()
	arr[-1] *= 2 ** count
	print(sum(arr))


t = int(input())
for i in range(t):
	w = int(input())
	a = list(map(int, input().split()))
	count = 0
	for j in range(len(a)):
		while a[j] % 2 == 0:
			a[j] = a[j] // 2
			count += 1
	s = 2 ** count
	a.sort()
	a[-1] *= s
	print(sum(a))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	c = 0
	for x in range(n):
		while a[x] % 2 == 0:
			a[x] //= 2
			c += 1
	a.sort()
	a[n - 1] *= pow(2, c)
	print(sum(a))


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	c = 0
	for x in a:
		while x % 2 == 0:
			x //= 2
			c += 1
		b.append(x)
	print(sum(b) + max(b) * (2 ** c - 1))
t = int(input())
for i in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	for i in range(len(a)):
		while a[i] % 2 == 0:
			cnt += 1
			a[i] = a[i] // 2
	a.sort()
	a[-1] = a[-1] * pow(2, cnt)
	print(sum(a))