即使在大学,学生也需要放松。这就是樱子老师决定去实地考察的原因。众所周知,所有学生都会排成一排。索引为 $$$i$$$ 的学生有一些感兴趣的主题,被描述为 $$$a_i$$$。作为一名老师,您希望尽量减少学生排队的干扰。
线路的干扰度定义为具有相同兴趣主题的相邻人员的数量。换句话说,干扰是满足 $$$a_j = a_{j + 1}$$$ 的索引 $$$j$$$ ($$$1 \le j < n$$$) 的数量。
为此,您可以选择索引 $$$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$$$。
输出
对于每个测试用例,输出您可以实现的最小可能的线路干扰。
示例
输入 #1
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
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$$$。