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

Даже в университете студентам нужно отдыхать. Именно поэтому учитель Сакурако решил организовать экскурсию. Известно, что все студенты будут идти в одну линию.

Студент с индексом $$$i$$$ имеет некоторую тему интереса, которая описывается как $$$a_i$$$. Как учитель, вы хотите минимизировать отвлечение в линии студентов.

Отвлечение линии определяется как количество соседей с одинаковой темой интереса. Другими словами, отвлечение — это количество индексов $$$j$$$ ($$$1 \le j < n$$$), таких что $$$a_j = a_{j + 1}$$$.

Чтобы сделать это, вы можете выбрать индекс $$$i$$$ ($$$1\le i\le n$$$) и поменять местами студентов на позициях $$$i$$$ и $$$n-i+1$$$. Вы можете выполнять любое количество обменов.

Ваша задача — определить минимальное отвлечение, которое вы можете достичь, выполняя описанную выше операцию любое количество раз.

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

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

Каждый набор входных данных описывается двумя строками.

  • Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — длина линии студентов.
  • Вторая строка содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1\le a_i\le n$$$) — темы интереса студентов в линии.

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

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

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

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

В первом примере нужно применить операцию к $$$i=2$$$, таким образом массив станет равен $$$[1, \textbf{2}, 1, \textbf{1}, 3]$$$, жирным выделены элементы, которые поменялись местами. Отвлечение этого массива равна $$$1$$$.

В четвёртом примере достаточно применить операцию к $$$i=3$$$, таким образом массив станет равен $$$[2, 1, \textbf{2}, \textbf{1}, 2, 4]$$$. Отвлечение этого массива равна $$$0$$$.

В восьмом примере достаточно применить операцию к $$$i=3$$$, таким образом массив станет равен $$$[1, 4, \textbf{1}, 5, \textbf{3}, 1, 3]$$$. Отвлечение этого массива равна $$$0$$$.