B. Уничтожение кольца
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определим циклическую последовательность размера $$$n$$$ как массив $$$s$$$ длины $$$n$$$, в котором $$$s_n$$$ является соседним с $$$s_1$$$.

У Muxii есть кольцо, представленное циклической последовательностью $$$a$$$ размера $$$n$$$.

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

Muxii может выполнять следующие операции, пока последовательность не станет пустой:

  • Выбрать элемент в $$$a$$$ и стереть его.

Например, если кольцо имеет вид $$$[1, 2, 4, 2, 3, 2]$$$, и Muxii стирает элемент $$$4$$$, то кольцо сотрёт один из элементов, равных $$$2$$$, и кольцо примет вид $$$[1, 2, 3, 2]$$$.

Muxii хочет найти максимальное количество операций, которые он может выполнить.

Заметим, что в кольце размером $$$1$$$ его единственный элемент не считается соседним с самим собой (поэтому он не стирается сразу).

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\leq n\leq 100$$$) — размер циклической последовательности.

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

Гарантируется, что $$$a_i\ne a_{i+1}$$$ для $$$1\leq i<n$$$.

Гарантируется, что $$$a_n\ne a_1$$$ при $$$n>1$$$.

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

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

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

В первом наборе входных данных вы можете сначала стереть второй элемент, а затем стереть оставшиеся элементы по одному в любом порядке. Всего можно выполнить эту операцию $$$4$$$ раза. Обратите внимание, что если сначала стереть первый элемент, то последовательность превратится в $$$[2,3,2]$$$, а затем сразу станет $$$[2,3]$$$.

Во втором наборе входных данных можно сначала стереть первый элемент, тогда последовательность превратится в $$$[2,1]$$$. Затем можно стереть все оставшиеся элементы по одному в любом порядке.