队伍

题目描述

Y 同学正在组织一次郊游活动。有 $N$ 名学生排成一列，依次编号为 $1$ 到 $N$。第 $i$ 名学生感兴趣的话题用一个整数 $A_i$ 表示。

为了让大家有更好的体验，Y 同学希望尽可能减小队伍的“干扰度”。队伍的干扰度定义为相邻两人感兴趣话题相同的对数。形式化地说，即满足 $1 \le j < N$ 且 $A_j = A_{j+1}$ 的整数 $j$ 的数量。

为了调整队伍，Y 同学可以进行任意次（包括零次）如下操作： 选择一个下标 $i$（$1 \le i \le N$），并交换队伍中第 $i$ 名学生与第 $N-i+1$ 名学生的位置（即交换 $A_i$ 与 $A_{N-i+1}$）。

请你编写程序，帮助 Y 同学计算出通过上述操作后，队伍可能达到的最小干扰度。

输入格式

第一行包含一个正整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行包含一个整数 $N$，表示学生队伍的长度。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，相邻两个整数之间由一个空格隔开，表示每名学生感兴趣的话题。

输出格式

输出共 $T$ 行。 对于每组测试数据，输出一行一个整数，表示队伍可能达到的最小干扰度。

样例

样例输入 #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

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le T \le 10^4$，$2 \le N \le 10^5$，$1 \le A_i \le N$，且所有测试数据中 $N$ 的总和 $\sum N \le 2 \times 10^5$。