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

ikrpprpp нашел массив $$$a$$$, состоящий из целых чисел. Ему нравится справедливость, поэтому он хочет сделать $$$a$$$ честным — то есть сделать его неубывающим. Для этого он может выполнить акт справедливости на индексе $$$1 \le i \le n$$$ массива, который заменит $$$a_i$$$ на $$$a_i ^ 2$$$ (элемент на позиции $$$i$$$ на его квадрат). Например, если $$$a = [2,4,3,3,5,3]$$$ и ikrpprpp решает выполнить акт справедливости на $$$i = 4$$$, то $$$a$$$ становится $$$[2,4,3,9,5,3]$$$.

Каково минимальное количество актов справедливости, необходимых для того, чтобы сделать массив неубывающим?

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

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. За ним следует описание наборов входных данных.

Для каждого набора входных данных первая строка содержит целое число $$$n$$$ — размер массива $$$a$$$. Вторая строка содержит $$$n$$$ ($$$1 \le n \le 2 \cdot 10 ^5$$$) целых числа $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \le a_i \le 10 ^ 6$$$).

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot {10}^5$$$.

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

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

Пример
Входные данные
7
3
1 2 3
2
3 2
3
3 1 5
4
1 1 2 3
3
4 3 2
9
16 2 4 2 256 2 4 2 8
11
10010 10009 10008 10007 10006 10005 10004 10003 10002 10001 10000
Выходные данные
0
1
-1
0
3
15
55
Примечание

В первом наборе входных данных нет необходимости выполнять акты справедливости. Массив сам по себе честен!

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

В пятом наборе входных данных ikrpprppp может выполнить акт справедливости на индексе 3, затем акт справедливости на индексе 2 и, наконец, еще один акт справедливости на индексе 3. После этого $$$a$$$ станет $$$[4, 9, 16]$$$.