题目描述

定义一个大小为 $n$ 的环状序列为一个长度为 $n$ 的数组 $s$，其中 $s_n$ 与 $s_1$ 相邻。

Muxii 有一个由大小为 $n$ 的环状序列 $a$ 表示的戒指。

然而，这个戒指本身讨厌相邻元素相等。因此，如果序列中任意时刻有两个相邻元素相等，其中一个会被立即擦除。最初序列中不包含相等的相邻元素。

Muxii 可以重复进行如下操作，直到序列变为空：

• 选择 $a$ 中的一个元素并将其擦除。

例如，如果戒指为 $[1, 2, 4, 2, 3, 2]$，Muxii 擦除元素 $4$，那么戒指会擦除其中一个等于 $2$ 的元素，戒指会变为 $[1, 2, 3, 2]$。

Muxii 想知道他最多可以进行多少次操作。

注意，对于大小为 $1$ 的环，其唯一的元素不被视为与自身相邻（因此不会被立即擦除）。

输入格式

每组测试包含多组测试用例。第一行包含一个整数 $t$（$1\leq t\leq 100$）——表示测试用例的数量。接下来是每组测试用例的描述。

每组测试用例的第一行包含一个整数 $n$（$1\leq n\leq 100$）——环状序列的大小。

每组测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\leq a_i\leq n$）——表示序列本身。

保证 $1\leq i<n$ 时 $a_i\ne a_{i+1}$。

当 $n>1$ 时，保证 $a_n\ne a_1$。

输出格式

对于每组测试用例，输出一个整数，表示 Muxii 最多可以进行的操作次数。

说明/提示

在第一个测试用例中，你可以先擦除第二个元素，然后按任意顺序依次擦除剩下的元素。总共可以进行 $4$ 次操作。注意，如果你先擦除第一个元素，则序列会变为 $[2,3,2]$，然后立即变为 $[2,3]$。

在第二个测试用例中，你可以先擦除第一个元素，序列变为 $[2,1]$。然后你可以按任意顺序依次擦除剩下的所有元素。

由 ChatGPT 4.1 翻译

样例

3
4
1 2 3 2
4
1 2 1 2
1
1

4
3
1