B. Сделай возрастающую
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$. Над ними можно совершать следующую операцию:

  • выбрать произвольный элемент $$$a_i$$$ ($$$1 \le i \le n$$$) и поделить его на $$$2$$$ (округляем вниз). Другими словами, можно заменить любой выбранный элемент $$$a_i$$$ на значение $$$\left \lfloor \frac{a_i}{2}\right\rfloor$$$ (где $$$\left \lfloor x \right\rfloor$$$ — округление вниз вещественного числа $$$x$$$).

Выведите минимальное количество операций, которое необходимо совершить, чтобы последовательность чисел стала строго возрастающей (то есть, чтобы было выполнено условие $$$a_1 \lt a_2 \lt \dots \lt a_n$$$). Или определите, что такую последовательность получить невозможно. Обратите внимание на то, что элементы нельзя менять местами. Единственная возможная операция описана выше.

Например, пусть $$$n = 3$$$ и задана последовательность чисел $$$[3, 6, 5]$$$. Тогда достаточно совершить над ней две операции:

  • записать вместо числа $$$a_2=6$$$ число $$$\left \lfloor \frac{6}{2}\right\rfloor = 3$$$ и получить последовательность $$$[3, 3, 5]$$$;
  • затем записать вместо числа $$$a_1=3$$$ число $$$\left \lfloor \frac{3}{2}\right\rfloor = 1$$$ и получить последовательность $$$[1, 3, 5]$$$.

Полученная последовательность является строго возрастающей, так как $$$1 \lt 3 \lt 5$$$.

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

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

Далее следуют описания наборов входных данных.

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

Во второй строке каждого набора входных данных записано ровно $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^9$$$).

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

Для каждого набора входных данных в отдельной строке выведите единственное число — минимальное количество операций, которое нужно совершить над последовательностью, чтобы она стала строго возрастающей. Если строго возрастающую последовательность невозможно получить, то выведите «-1».

Пример
Входные данные
7
3
3 6 5
4
5 3 2 1
5
1 2 3 4 5
1
1000000000
4
2 8 7 5
5
8 26 5 21 10
2
5 14
Выходные данные
2
-1
0
0
4
11
0
Примечание

Первый набор входных данных разобран в условии.

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

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