A. Дели и преумножай
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Василия есть массив из $$$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$$$

Помогите Василию найти максимальную сумму элементов массива, которую он сможет добиться, используя описанную последовательность операций.

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$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
Примечание

В первом тестовом примере оптимальный порядок выглядит следующим образом:

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