题目描述

即使在大学里，学生们也需要放松。这就是为什么樱子的老师决定组织一次郊游。已知所有学生将排成一列。第 $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$。

约束条件

• $1 \le t \le 10^4$
• $2 \le n \le 10^5$
• $1 \le a_i \le n$
• 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$
• 所有输入值均为整数。