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

В один день BThero решил поиграться с массивами и придумал следующую задачу:

Вам дан массив $$$a$$$, состоящий из $$$n$$$ положительных целых чисел. Массив нумеруется с $$$1$$$ до $$$n$$$. Вы выполняете следующую процедуру ровно один раз:

  • Вы создаете новый массив $$$b$$$, состоящий из $$$2n$$$ положительных целых чисел, где для каждого $$$1 \le i \le n$$$ выполнено условие $$$b_{2i-1}+b_{2i} = a_i$$$. Например, для $$$a = [6, 8, 2]$$$ можно создать $$$b = [2, 4, 4, 4, 1, 1]$$$.
  • Вы склеиваете подряд идущие одинаковые числа в $$$b$$$. Например, $$$b = [2, 4, 4, 4, 1, 1]$$$ станет $$$b = [2, 4, 1]$$$.

Найдите и выведите минимальное возможное значение $$$|b|$$$ (размер массива $$$b$$$), которое вы можете получить в конце процедуры. Можно показать, что с заданными ограничениями всегда есть хотя бы один способ построить массив $$$b$$$.

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

В первой строке входного файла задано одно целое число $$$T$$$ ($$$1 \le T \le 5 \cdot 10^5$$$) — кол-во наборов входных данных. Далее следуют $$$T$$$ наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$2 \le a_i \le 10^9$$$).

Гарантируется, что $$$\sum{n}$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

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

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

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