D. diss_quack и игра с массивом
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ из $$$n$$$ целых чисел. Алиса и Боб будут играть в игру с этим массивом.

Перед началом игры с Бобом Алиса может увеличить любой элемент массива на $$$1$$$ любое количество раз, причём каждое увеличение считается за один ход.

После этого начинается игра, и Алиса с Бобом ходят по очереди, при этом Боб ходит первым. На ходе Боба он может выбрать любые два индекса $$$i$$$ и $$$j$$$ и поменять местами элементы массива на этих позициях (заметьте, что Боб может выбрать $$$i = j$$$, и тогда после обмена массив не изменится).

На ходе Алисы, если $$$a_1$$$ чётно, она находит наибольшее $$$j \leq |a|$$$ такое, что $$$a_i$$$ чётно для всех $$$i \leq j,$$$ а затем присваивает $$$a_i := a_i/2$$$ для всех $$$i \leq j.$$$ Иначе она присваивает $$$a_1 := a_1 - 1.$$$ Если какой-либо элемент становится равным нулю, он автоматически удаляется из массива (а остальные элементы перенумеровываются соответствующим образом).

Игра заканчивается, когда массив становится пустым.

Алиса хочет минимизировать число своих ходов, а Боб хочет максимизировать число ходов Алисы. Заметьте, что число ходов — это сумма числа начальных увеличений и числа ходов Алисы после этого.

Сколько ходов сделает Алиса при оптимальной игре?

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных дано одно целое число $$$n \, (1 \le n \le 10^5)$$$ — длина массива.

Во второй строке каждого набора входных данных даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_{n}\,(1 \le a_i \le 10^5)$$$ — элементы массива.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — число ходов, которое сделает Алиса, если оба игрока играют оптимально.

Пример
Входные данные
4
3
1 2 3
4
2 2 2 2
5
6 8 2 4 1
8
1 3 5 7 9 11 13 15
Выходные данные
6
5
12
35
Примечание

В первом случае Алиса решает не увеличивать ни один элемент в начале. На первом ходе Боб выбирает $$$i = j = 1$$$ (то есть не меняет элементы местами). Затем Алиса вычитает $$$1$$$ из $$$a_1,$$$ и массив становится $$$[2,3]$$$. Далее Боб снова выбирает $$$i = j = 1.$$$ Алиса делит $$$a_1$$$ на $$$2$$$, и массив становится $$$[1,3]$$$. Боб снова выбирает $$$i = j = 1.$$$ Алиса снова вычитает из $$$a_1,$$$ и массив становится $$$[3]$$$. Теперь Боб обязан выбрать $$$i = j = 1,$$$ а Алисе требуется ещё $$$3$$$ хода, чтобы сделать массив пустым. Итого Алиса делает $$$6$$$ ходов. Можно показать, что это и есть результат оптимальной игры.

Во втором наборе входных данных Алиса снова решает не увеличивать ни один элемент в начале. Можно показать, что при оптимальной игре Алиса делает $$$5$$$ ходов.