C. 樱子的郊游
每个测试点时间限制：2 秒
内存限制：256 兆字节

即使在大学，学生也需要放松。因此樱子的老师决定组织一次郊游。
已知所有学生将排成一列。索引为 $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$。

输出
对于每个测试用例，输出通过上述操作能达到的最小扰动值。

示例
输入

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  
2  
1  
0  
0  
1  
1  
0  
2  

注意

• 在第一个示例中，需要对 $i=2$ 应用操作，数组变为 $[1,2,1,1,3]$（加粗部分表示交换过的学生）。该数组的扰动为 $1$。
• 在第四个示例中，对 $i=3$ 应用操作足够，数组变为 $[2,1,2,1,2,4]$，扰动为 $0$。
• 在第八个示例中，对 $i=3$ 应用操作足够，数组变为 $[1,4,1,5,3,1,3]$，扰动为 $0$。