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

Вам дан массив $$$a$$$ длины $$$n$$$. Определим равность массива как количество индексов $$$1 \le i \le n - 1$$$ таких, что $$$a_i = a_{i + 1}$$$. Мы можем выполнять следующую операцию:

  • Выберите любые два целых числа $$$i$$$ и $$$x$$$ такие, что $$$1 \le i \le n - 1$$$ и $$$1 \le x \le 10^9$$$. После этого, сделайте $$$a_i$$$ и $$$a_{i + 1}$$$ равными $$$x$$$.

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

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

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

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

Вторая строка каждого тестового примера содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)  — элементы массива.

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

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

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

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

В первом наборе входных данных мы можем выбрать $$$i=2$$$ и $$$x=2$$$, получив $$$[1, 2, 2, 1, 1]$$$. Затем мы можем выбрать $$$i=3$$$ и $$$x=3$$$, получив $$$[1, 2, 3, 3, 1]$$$.

Во втором наборе входных данных мы можем выбрать $$$i=3$$$ и $$$x=100$$$, получив $$$[2, 1, 100, 100, 2]$$$.