B. Flower Ring
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After arriving at Mary's house, Ian gifted a ring of flowers to Mary. The ring of flowers consists of different kinds of flowers. For convenience, we assign a number to each kind of flower and denote the ring by an array of integers $$$a_1,a_2,...,a_n$$$ where $$$n$$$ is the number of flowers in the ring, such that $$$a_i=a_j$$$ if and only if the $$$i$$$-th flower is of the same kind as the $$$j$$$-th flower.

Mary calls a ring of flowers supreme if, for any two adjacent flowers, their kinds are not the same. Note that the $$$n$$$-th flower is adjacent to the first flower. In other words, there does not exist $$$i$$$ such that $$$a_i=a_{i+1}$$$ with indices taken modulo $$$n$$$. An exception to this is that a ring which consists of only $$$1$$$ flower is always regarded as supreme.

Mary wants to cut the ring of flowers which Ian had gifted her into several chains of flowers, and form a new ring of flowers with each chain by joining both of its ends. She wants all of the newly formed rings to be supreme. What is the minimum number of rings Mary needs to form to meet her requirement?

Input

The first line consists of an integer $$$t$$$ ($$$1\le t\le 10^4$$$), the number of test cases.

The first line of each test case consists of a single integer $$$n$$$ ($$$1\le n\le 3\cdot10^5$$$), the number of flowers in the ring.

The second line of each test case consists of $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ($$$1\le a_i\le n$$$), where $$$a_i$$$ is the kind of the $$$i$$$-th flower.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3\cdot10^5$$$.

—

Tests in subtasks are numbered $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.

Tests $$$1-20$$$ satisfy no additional constraints.

Output

For each test case, output an integer, the minimum number of rings that Mary needs to form such that all rings are supreme.

Example
Input
5
1
1
3
1 1 1
4
1 1 2 2
7
1 2 2 6 7 3 4
7
1 1 2 1 1 2 3
Output
1
3
2
2
4
Note

Explanation for the first three cases: (Note that the number on the circle representing the $$$i$$$-th flower is $$$i$$$, and the background colour of the circle is green if $$$a_i=1$$$, and blue if $$$a_i=2$$$.)

Case 1: The ring is already supreme. So the answer is $$$1$$$.

Case 2: The optimal way is to have three rings, each with one flower in it. So the answer is $$$3$$$.

Case 3: We can cut between flower $$$1$$$ and $$$4$$$, and between flower $$$2$$$ and $$$3$$$, to attain the optimal number of two rings. The answer is $$$2$$$.

—

Problem Idea: culver0412

Problem Preparation: culver0412

Occurrences: Novice B