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

Вам дана последовательность $$$a$$$, состоящая из $$$n$$$ натуральных чисел.

За одну операцию вы можете разбить любое число последовательности на два новых натуральных числа. Остальные элементы последовательности не меняются.

Например: $$$a=[3,2,1]$$$, можно разбить $$$a_1=3$$$ на $$$1$$$ и $$$2$$$, получая $$$a=[1,2,2,1]$$$.

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

Палиндром — это последовательность, которая читается одинаково в обоих направлениях.

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

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

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

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

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

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

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

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

В первом наборе входных данных можно использовать следующую операцию: $$$[\underline{3},2,1]\xrightarrow{}[1,2,2,1]$$$.

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

В третьем наборе входных данных можно использовать следующие операции:$$$[\underline{6},5,4,3,2,1]\xrightarrow{}[1,\underline{5},5,4,3,2,1] \xrightarrow{}[1,2,3,\underline{5},4,3,2,1] \xrightarrow{}[1,2,3,4,1,4,3,2,1]$$$.