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

Перед своей последней миссией Ктолли задает Виллему три вопроса.

Первый из них таков: если конец неизбежен, сколько времени пройдет, пока ничего не останется?

Виллем не может ответить ей напрямую. Вместо этого он записывает $$$n$$$ целых положительных чисел $$$a_1,a_2,\ldots,a_n$$$.

Каждая операция занимает одну секунду. В ходе одной операции Виллем делает следующее:

  • Выбирает индекс $$$p$$$ ($$$1\le p\le n$$$);
  • Затем заменяет $$$a_p$$$ на $$$\left\lfloor\dfrac{a_p}{2}\right\rfloor$$$, а для каждого $$$i\ne p$$$ заменяет $$$a_i$$$ на $$$\left\lceil\dfrac{a_i}{2}\right\rceil$$$. Все замены выполняются одновременно.

Найдите минимальное количество секунд, необходимое для того, чтобы все $$$n$$$ целых чисел стали равны $$$0$$$.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le10^9$$$) — начальные числа.

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

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

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

Пример
Входные данные
5
1
3
3
1 1 1
3
1 2 4
2
5 2
6
1 2 3 4 5 6
Выходные данные
2
3
3
3
6
Примечание

В первом наборе входных данных единственное целое число изменяется по последовательности $$$3\to1\to0$$$, поэтому ответ равен $$$2$$$.

Во втором наборе входных данных целое число, равное $$$1$$$, принимает значение $$$0$$$ только тогда, когда выбирается его индекс. Таким образом, требуется не менее $$$3$$$ секунд, и достаточно выбрать каждый индекс один раз.

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

  1. Выбрать $$$p=1$$$: $$$[1,2,4]\to[0,1,2]$$$;
  2. Выбрать $$$p=2$$$: $$$[0,1,2]\to[0,0,1]$$$;
  3. Выбрать $$$p=3$$$: $$$[0,0,1]\to[0,0,0]$$$.

В четвёртом наборе входных данных оптимальная последовательность: $$$[5,2]\to[2,1]\to[1,0]\to[0,0]$$$, где выбранные индексы равны $$$1$$$, $$$2$$$ и $$$1$$$.