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

Поликарп называет массив плотным, если в любой паре двух соседних элементов больший элемент не более чем в два раза превышает меньший. Более формально, для любого $$$i$$$ ($$$1 \le i \le n-1$$$) должно быть выполнено условие: $$$$$$\frac{\max(a[i], a[i+1])}{\min(a[i], a[i+1])} \le 2$$$$$$

Например, массивы $$$[1, 2, 3, 4, 3]$$$, $$$[1, 1, 1]$$$ и $$$[5, 10]$$$ — плотные. А массивы $$$[5, 11]$$$, $$$[1, 4, 2]$$$, $$$[6, 6, 1]$$$ — нет.

Вам дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Какое минимальное количество чисел необходимо добавить в массив, чтобы он стал плотным? Вставлять числа можно в любое место массива. Если массив уже является плотным, то числа добавлять не надо.

Например, если $$$a=[4,2,10,1]$$$, то ответ равен $$$5$$$, а сам массив после вставки в него элементов может выглядеть так: $$$a=[4,2,\underline{\textbf{3}},\underline{\textbf{5}},10,\underline{\textbf{6}},\underline{\textbf{4}},\underline{\textbf{2}},1]$$$ (есть и другие оптимальные способы построить плотный массив $$$a$$$).

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

В первой строке содержится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$). Далее следуют $$$t$$$ наборов входных данных.

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

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 50$$$).

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

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

Пример
Входные данные
6
4
4 2 10 1
2
1 3
2
6 1
3
1 4 2
5
1 2 3 4 3
12
4 31 25 50 30 20 34 46 42 16 15 16
Выходные данные
5
1
2
1
0
3
Примечание

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

Во втором наборе входных данных можно вставить один элемент, $$$a=[1,\underline{\textbf{2}},3]$$$.

В третьем наборе входных данных можно вставить два элемента, $$$a=[6,\underline{\textbf{4}},\underline{\textbf{2}},1]$$$.

В четвертом наборе входных данных можно вставить один элемент, $$$a=[1,\underline{\textbf{2}},4,2]$$$.

В пятом наборе входных данных массив $$$a$$$ уже плотный.