题目描述

对于一个六面骰子来讲，其上的数字 $x$ 和 $7-x$ 位于相对的边上。：

• $1$ 的对立面为 $6$。
• $2$ 的对立面为 $5$。
• $3$ 的对立面为 $4$。

给你一个长度为 $n$ 的序列 $a$，其中 $1\leq a_i\leq 6$。定义一个序列为骰子序列，当且仅当：

• 所有相邻元素对都位于立方体的相邻 $^{\text{∗}}$ 面上。
  • 即对于所有的 $i$ 当 $1\leq i\leq n-1$，$a_i$ 和 $a_{i+1}$ 不是骰子里的对立面的两个数字。且 $a_i\neq a_{i+1}$。

例如， $[1,4,2]$ 是一个掷骰子序列，而 $[3,4,6,3]$ 不是，因为 $3$ 和 $4$ 不在骰子的相邻面上。此外， $[2,2,4]$ 也不是掷骰子序列，因为 $2$ 和 $2$ 位于骰子的同一面（不相邻）。

给定一个从 $1$ 到 $6$ 的由 $n$ 个整数组成的序列 $a$ ，可以执行以下任意次数（可能为零）的运算。

• 选择索引 $1 \le i \le n$ 和整数 $1 \le x \le 6$ 。然后，将 $a_i$ 的值更改为 $x$ 。

请计算使 $a$ 成为骰子序列所需的最少操作次数。

输入格式

本题有多组数据

第一行输入一个整数 $t$ 表示测试数据组数，对于每一组数据：

• 第一行输入一个整数 $n$ 表示序列的长度。
• 第二行输入一个长度为 $n$ 的序列 $a$。

输出格式

对于每一组数据，输出一个整数表示答案。

4
3
1 4 2
4
3 4 6 3
10
6 1 4 3 1 3 2 5 4 4
3
1 1 1

0
1
4
1

提示

样例解释

对于第一个测试案例，序列 $a$ 是 $[1,4,2]$ 。由于这已经是一个骰子序列，因此答案为 $0$ 。

对于第二个测试案例，序列 $a$ 是 $[3,4,6,3]$ 。

恰好改变一个元素，就可以得到 $[3,\textcolor{red}{5},6,3]$ ，这是一个骰子序列。

对于第三个测试用例，序列 $a$ 是 $[6,1,4,3,1,3,2,5,4,4]$ 。

恰好改变 $4$ 个元素，可以得到 $[\textcolor{red}{5},1,4,\textcolor{red}{2},1,3,2,\textcolor{red}{1},\textcolor{red}{5},4]$ ，这是一个骰子序列。

数据范围

对于 $100\%$ 的数据满足：$1\leq t\leq 10^4$，$1\leq n\leq 3\times 10^5$，$1\leq a_i\leq 6$。保证 $\sum n\leq 3\times 10^5$。

• 子任务 1 (20分)：$n \le 10$。
• 子任务 2 (30分)：$n \le 1000$。
• 子任务 3 (50分)：无特殊限制。