CF1761B.Elimination of a Ring

Define a cyclic sequence of size $n$ as an array $s$ of length $n$, in which $s_n$ is adjacent to $s_1$.

Muxii has a ring represented by a cyclic sequence $a$ of size $n$.

However, the ring itself hates equal adjacent elements. So if two adjacent elements in the sequence are equal at any time, one of them will be erased immediately. The sequence doesn't contain equal adjacent elements initially.

Muxii can perform the following operation until the sequence becomes empty:

• Choose an element in $a$ and erase it.

For example, if ring is $[1, 2, 4, 2, 3, 2]$, and Muxii erases element $4$, then ring would erase one of the elements equal to $2$, and the ring will become $[1, 2, 3, 2]$.

Muxii wants to find the maximum number of operations he could perform.

Note that in a ring of size $1$, its only element isn't considered adjacent to itself (so it's not immediately erased).

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

Muxii 拥有一个由长度为 $n$ 的循环序列 $a$ 表示的环形结构。

然而，该环形结构本身厌恶相邻且相等的元素。因此，若序列中任意时刻存在两个相邻且相等的元素，则其中一个会立即被擦除。初始时，该序列中不包含相邻且相等的元素。

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

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

例如，若环形结构为 $[1, 2, 4, 2, 3, 2]$，而 Muxii 擦除了元素 $4$，则环形结构将立即擦除一个值为 $2$ 的相邻元素（因擦除 $4$ 后产生相邻相等对 $2,2$），最终环形结构变为 $[1, 2, 3, 2]$。

Muxii 希望找出他最多能执行的操作次数。

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

Each test contains multiple test cases. The first line contains a single integer $t$ ($1\leq t\leq 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1\leq n\leq 100$) — the size of the cyclic sequence.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\leq a_i\leq n$) — the sequence itself.

It's guaranteed that $a_i\ne a_{i+1}$ for $1\leq i \lt n$.

It's guaranteed that $a_n\ne a_1$ when $n \gt 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 \lt n$，有 $a_i\ne a_{i+1}$。

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

For each test case, output a single integer — the maximum number of operations Muxii can perform.

对于每个测试用例，输出一个整数——Muxii 能执行的最大操作次数。

In the first test case, you can erase the second element first, then erase the remaining elements one by one in any order. In total, you can perform the operation $4$ times. Note that if you erase the first element first, then the sequence will be turned into $[2,3,2]$ and then immediately become $[2,3]$.

In the second test case, you can erase the first element first, then the sequence becomes $[2,1]$. Then you can erase all remaining elements one by one in any order.

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

在第二个测试用例中，你可以先删除第一个元素，此时序列变为 $[2,1]$；然后可以以任意顺序逐一删除所有剩余元素。