Elimination of a Ring
Contest: Pinely Round 1 (Div. 1 + Div. 2)
Difficulty rating: 1000
Tags: constructive algorithms, greedy, implementation

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).

Input format:
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<n$$$.

It's guaranteed that $$$a_n\ne a_1$$$ when $$$n>1$$$.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3
4
1 2 3 2
4
1 2 1 2
1
1

Example output:
4
3
1

Editorial:
Hint
Do we need more than $$$3$$$ types of elements? Try to solve the problem with $$$a_i\leq 3$$$.
Solution
First of all, when there're only $$$2$$$ types of elements appearing in the sequence, the answer would be $$$\frac{n}2+1$$$.
Otherwise, the conclusion is that we can always reach $$$n$$$ operations when there are more than $$$2$$$ types of elements appearing in the sequence.
The proof is given below: When the length of the sequence is greater than $$$3$$$, there will always be a pair of positions $$$(i,j)$$$, such that $$$a_i=a_j$$$ and $$$a_i$$$ has two different neighboring elements. Then we can erase $$$a_i$$$ and then the problem is decomposed into a smaller one. If there do not exist such pairs, then we can infer that there exists at least $$$1$$$ element which appeared only once in the sequence. If there exists such element $$$b$$$, then we can continuously erase all the elements next to $$$b$$$, then erase $$$b$$$ at last. When the length $$$n$$$ of the sequence is less than $$$3$$$, it is clear that there will be exactly $$$n$$$ operations as well.
So we only need to check the number of elements that appeared in the sequence of length $$$n$$$. If the number is $$$2$$$, the answer will be $$$\frac n2 + 1$$$. Otherwise, the answer equals $$$n$$$.