У Василия есть массив из $$$n$$$ чисел $$$a_1, a_2, \dots, a_n$$$. Он может любое количество раз выполнить следующую последовательность операций:
- выбрать два любых элемента массива $$$a_i$$$ и $$$a_j$$$, где $$$a_i$$$ должно делиться нацело на $$$2$$$
- $$$a_i = \frac{a_i}{2}$$$
- $$$a_j = a_j \cdot 2$$$
Помогите Василию найти максимальную сумму элементов массива, которую он сможет добиться, используя описанную последовательность операций.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют наборы входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ $$$(1 \le n \le 15)$$$ — количество элементов в массиве Василия.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i < 16)$$$ — описание массива Василия.
Для каждого набора входных данных выведите максимальную сумму элементов массива после оптимального применения последовательности операций.
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
В первом тестовом примере оптимальный порядок выглядит следующим образом:
- Выбрать $$$i = 2$$$ и $$$j = 1$$$. После выполнения последовательности операций $$$a_2 = \frac{4}{2} = 2$$$ и $$$a_1 = 6 \cdot 2 = 12$$$, массив будет следующим: [12, 2, 2].
- Выбрать $$$i = 2$$$ и $$$j = 1$$$. После выполнения последовательности операций $$$a_2 = \frac{2}{2} = 1$$$ и $$$a_1 = 12 \cdot 2 = 24$$$, массив будет следующим: [24, 1, 2].
- Выбрать $$$i = 3$$$ и $$$j = 1$$$. После выполнения последовательности операций $$$a_3 = \frac{2}{2} = 1$$$ и $$$a_1 = 24 \cdot 2 = 48$$$, массив будет следующим: [48, 1, 1].
Итоговый ответ $$$48 + 1 + 1 = 50$$$.
В третьем тестовом примере нет возможности поменять сумму элементов, поэтому ответ $$$10$$$.
