结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

程老师的花坛边缘围着一圈花盆，盆数记为 $n$，沿花坛走一圈就依次经过这些花盆。每个花盆里种着一种花，颜色用一个正整数表示；颜色编号相同就当作同一种花。花盆是可以搬动的：程老师随时能把这一圈 $n$ 个位置上的花盆全部取下、再任意摆回去，花盆里种的是什么花不会因为搬动而改变，花盆原先摆在哪儿也不影响这件事。

摆好之后，程老师要求花坛上任意两个紧挨着的花盆里都不是同一种花。这里的"紧挨着"包含沿花坛走满一圈时最后一盆与第一盆的那一次相邻。

有时候光靠搬动达不到这个要求，程老师就得去花市换掉若干盆花。换掉一盆花指的是：把这一盆里原来的花扔掉，换成任意一种颜色的新花，新花的颜色可以是他的花坛里目前没有的颜色；一盆花只换一次，也只换成一盆。换完以后，换过的盆和没换过的盆一起，仍然可以任意搬动摆放。程老师希望换掉的花盆数量最少。

花坛的维护是一段一段来的。账本上记着 $q$ 段记录，每段记录给出当时一圈里各盆花的颜色，各段记录之间互不影响。对每段记录，请算出程老师最少需要换掉几盆花。

输入格式

从文件 ring.in 中读入数据。

• 第一行一个整数 $q$，表示记录段数；
• 接下来依次给出 $q$ 段记录，每段两行：第一行一个整数 $n$，表示这一段记录里花盆的数量；第二行 $n$ 个整数 $c_1, c_2, \dots, c_n$，依次给出这 $n$ 个花盆里各种的是什么颜色的花，给出的先后次序与花盆在花坛上的摆法无关。

输出格式

输出到文件 ring.out 中。

输出 $q$ 行，每行一个整数，依次表示每段记录中最少需要换掉的花盆数量。

样例

2
6
1 1 1 1 2 3
5
1 1 2 2 3

1
0

样例 1 解释

第一段记录里颜色 $1$ 的花有 $4$ 盆。把 $4$ 盆同一种颜色的花摆在一圈上，每两盆之间至少要夹进一盆别的花，一圈至少要有 $8$ 个位置才摆得下，而这段记录只有 $6$ 个位置，所以这段记录里怎么搬动都不行，必须换花。换掉一盆颜色 $1$ 的花之后，同一种颜色的花最多还剩 $3$ 盆，$6$ 个位置正好容得下，换 $1$ 盆就够了。第二段记录里颜色 $1$ 与颜色 $2$ 各有 $2$ 盆、颜色 $3$ 有 $1$ 盆，把前两种花各取一盆相间摆开，剩下的一盆放在余下的位置上，一圈上相邻两盆的颜色就都不同，不需要换花。

3
7
1 1 1 1 1 2 3
2
1 1
6
1 1 1 2 3 4

2
1
0

样例 2 解释

第二段记录里一共两个花盆，它们在一圈上互为彼此紧挨着的那一盆，两盆又是同一种花，只能换掉其中一盆。

数据范围

对于所有测试数据，保证：

• $1 \le q \le 10^5$；
• $2 \le n \le 10^6$，且同一次输入里各段记录的 $n$ 之和不超过 $10^6$；
• $1 \le c_i \le n$。

各测试点的约束如下：

• 特殊性质 A：对每段记录，程老师都可以只靠搬动花盆把花坛摆成相邻两盆都不是同一种花的样子。
• 特殊性质 B：对每段记录，所有花盆里的花颜色都相同。