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

Рассмотрим следующий куб $$$D$$$, на котором числа $$$x$$$ и $$$7-x$$$ находятся на противоположных гранях:

Изображение сгенерировано Nano Banana Pro.

Последовательность $$$b$$$ целых чисел от $$$1$$$ до $$$6$$$ называется последовательностью бросков кубика, если она удовлетворяет следующему условию:

  • Все пары соседних элементов находятся на смежных$$$^{\text{∗}}$$$ гранях кубика.

Например, $$$[1,4,2]$$$ является последовательностью бросков кубика, в то время как $$$[3,4,6,3]$$$ не является таковой, потому что $$$3$$$ и $$$4$$$ находятся не на смежных гранях кубика. Кроме того, $$$[2,2,4]$$$ не является последовательностью бросков кубика, потому что $$$2$$$ и $$$2$$$ находятся на одной (не смежной) грани кубика.

Дана последовательность $$$a$$$ из $$$n$$$ целых чисел от $$$1$$$ до $$$6$$$, вы можете выполнять следующую операцию любое количество раз (возможно, ноль).

  • Выберите индекс $$$1 \le i \le n$$$ и целое число $$$1 \le x \le 6$$$. Затем измените значение $$$a_i$$$ на $$$x$$$.

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

$$$^{\text{∗}}$$$Две грани кубика $$$S$$$ и $$$T$$$ называются смежными, если они имеют ровно одно общее ребро кубика. Обратите внимание, что это условие также подразумевает $$$S \neq T$$$.

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

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

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

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 6$$$).

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

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

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

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

В первом примере последовательность $$$a$$$ равна $$$[1,4,2]$$$. Поскольку это уже последовательность бросков кубика, ответ равен $$$0$$$.

Во втором примере последовательность $$$a$$$ равна $$$[3,4,6,3]$$$.

Изменив ровно один элемент, вы можете получить $$$[3,\color{red}{5},6,3]$$$, что является последовательностью бросков кубика.

В третьем примере последовательность $$$a$$$ равна $$$[6,1,4,3,1,3,2,5,4,4]$$$.

Изменив ровно $$$4$$$ элемента, вы можете получить $$$[\color{red}{5},1,4,\color{red}{2},1,3,2,\color{red}{1},\color{red}{5},4]$$$, что является последовательностью бросков кубика.